Explicit formula for the n-th term of a permutation

[Tomasz Ordowski]

Regarding A387016.

FORMULA: a(n) = (k - 2^m)*2^m + 1 = k*2^m - 4^m + 1,                                   

 where 1 < 2^m < k odd, for n = A001855((k-1)/2) + m.

     PROOF: it is quite sufficient to note that 

A001855(n) = Sum_{j=1..n} floor(log_2(2j-1)). QED.

See https://oeis.org/history/view?seq=A387016&v=77 

See also other definitions in the comments and formulas section.

Similarly; A386386(n) = (k - 2^m)*2^(m-1) - 1 = k*2^(m-1) - 2^(2m-1) - 1, 

where 1 < 2^m < k odd, for n = A001855((k-1)/2) + m - 1 (due to offset 0).  

It should also be noted that the second formula for the sequence A386220

is an inverse of the formula for permutation A386386 of all integers >= 0,

which will be useful for formulating a formula of inverse permutation:

0, 2, 1, 7, 3, 4, 5, 20, 8, 6, 11, 10, 14, 9, 17, 53, 21, 12, 25, 13, ...

Cf. https://oeis.org/history/view?seq=A386386&v=34 

Best, 

Tom Ordo (3/3)

____________

https://oeis.org/draft?user=Thomas%20Ordowski

[Tomasz Ordowski]

PS. It is worth citing the Discussion under A387016, as a justification for this and not another choice of the formula for appropriate permutation.

Sat Aug 23

04:56

M. F. Hasler: It should be clarified how this is meant to be a permutation of the odd integers. The usual definition of a permutation of the set S is a bijection of S into S.

05:05

M. F. Hasler: Also, why not start with a(0)=1 in oder to get a "permutation" (in the same sense) of *all* odd integers > 0, instead of starting with 3? (One would have to allow m=0 in that case, but as the formula says, m must always be such that 2^m is the largest power of 2 <= n, so it could and maybe should be defined that way. I think it is more natural to use that definition and be able to include 1, rather than to exclude 1 just to avoid necessity of stating the (given) maximality of m explicitly.)

07:30

Thomas Ordowski: One can obtain a permutation of all positive odd numbers by simply changing the formula to (k-2^m)*2^m-1, where 1 < 2^m < k odd. However, the formula (k-2^m)*2^m+1, where 1 < 2^m < k odd, is more basic with respect to the sorting numbers, where A(1) = 0. This gives a more natural definition of the explicit formula for the n-th term a(n) of the permutation of all odd numbers > 1 (see my formula). I use this first formula, slightly modified, namely (k-2^m)*2^(m-1)-1, [where 1 < 2^m < k odd], to define the permutation of all integers >= 0. It can be proven that all of these representations are unique, so these formulas give the corresponding permutations that I mention here.  [End of quote].                                                                

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/af9eb0be-86dc-4c6a-8047-b0391b0e1732n%40googlegroups.com.

[Tomasz Ordowski]

A386386

Permutation of all nonnegative integers given by (k - 2^m)*2^(m-1) - 1, where 1 < 2^m < k odd, sorted first by k then by m.

0

0, 2, 1, 4, 5, 6, 9, 3, 8, 13, 11, 10, 17, 19, 12, 21, 27, 14, 25, 35, 7, 16, ...

(list; graph; refs; listen; history; published version; edit; text; internal format)

OFFSET

0,2

COMMENTS

Every integer >= 0 can be written uniquely in the form (k - 2^m)*2^(m-1) - 1, where 1 < 2^m < k odd. Cf. A387016 (permutation of all odd numbers > 1).

In this sequence, even numbers appear in ascending order, and odd numbers are mixed accordingly.

FORMULA

a(n) = (A387016(n+1)-1)/2 - 1.

a(n) = (k-2^m)*2^(m-1)-1 = k*2^(m-1)-2^(2m-1)-1, where 1 < 2^m < k odd, for n = A001855((k-1)/2) + m - 1. Note that the sorting number A001855(t) = Sum_{j=1..t} floor(log_2(2j-1)). Hence a(A001855(n)) = 2n.

MATHEMATICA

Table[(k-2^m)*2^(m-1)-1, {k, 3, 50, 2}, {m, 1, Log2[k]}] // Flatten (* Amiram Eldar, Aug 21 2025 *)

CROSSREFS

Cf. A001477, A001855, A387016, A386220.

KEYWORD

nonn,look,changed

AUTHOR

Thomas Ordowski, Aug 20 2025

[Tomasz Ordowski]

Sun Aug 24

02:27

Kevin Ryde: At "Note", normally don't want more than a hint at the nature of another sequence.  Wouldn't have it's full sum definition.

02:29

Kevin Ryde: For an individual term formula, what you want is to get from n to k.  By my reckoning it may be k = 2*A030530(n)+1.  That sequence is (not unreasonably!) made by repetitions of each natural number (according as its bit length).

02:31

Kevin Ryde: A001855 "sorting numbers", meaning cumulative bit length, can get in as the n which is the first of a given k, much as you have, so that m = n - A001855((k-1)/2), or whatever name might give to (k-1)/2.

02:32

Kevin Ryde: In any case, which in keyword "new" time after approval, you can edit freely without signatures.  Esp if the approval was a touch quicker than you expected :).

02:37

Kevin Ryde: I contemplated what n is the first of a given bit length M = floor(log2(k)), since the pattern is m = 1..M (inclusive) commences at that point.  (Through to the next k bit length, next M).  I made that point n = F(M) = (M-2)*2^(M-1) + 2, which is a little variation on A188716.  So the task is to find M largest with n >= F(M), and there blocks of m = 1..M starting from, umm, k = 2^M + 1.  (A division (n-F(M))/M says how far into those repetitions, etc etc.)

02:37

Thomas Ordowski: Okay, I deleted my signature, thanks! All your comments are welcome here.

02:49

Thomas Ordowski: Yes, it's worth thinking about what Kevin wrote...

02:50

Thomas Ordowski: Research in progress.

sob., 23 sie 2025 o 13:55 Tomasz Ordowski <tomaszo...@gmail.com> napisał(a):