A309773 n directly precedes a(n) in Sharkovskii ordering.

1, 5, 2, 7, 10, 9, 4, 11, 14, 13, 20, 15, 18, 17, 8, 19, 22, 21, 28, 23, 26, 25, 40, 27, 30, 29, 36, 31, 34, 33, 16, 35, 38, 37, 44, 39, 42, 41, 56, 43, 46, 45, 52, 47, 50, 49, 80, 51, 54, 53, 60, 55, 58, 57, 72, 59, 62, 61, 68, 63, 66, 65, 32, 67, 70, 69, 76

Offset

2,2

Comments

Sharkovskii ordering is as follows:

- numbers that are not powers of two come first,

ordered by increasing 2-adic valuation and then by increasing value,

- powers of two come last, in decreasing order.

The number 3 is the least element of Sharkovskii ordering; it is the only number that does not appear in the sequence.

The number 1 is the greatest element of Sharkovskii ordering; it does not precede any other number, hence the offset of the sequence is 2.

Links

Table of n, a(n) for n=2..68.

Wikipedia, Sharkovskii's theorem

Formula

a(2^(k+1)) = 2^k for any k >= 0.

a((2*m+1)*2^k) = (2*m+3)*2^k for any m > 0 and k >= 0.

Prog

(PARI) a(n) = if (hammingweight(n)==1, n/2, my (v=valuation(n, 2)); n+2*2^v)
(Python)
def A309773(n): return n>>1 if (m:=(~n & n-1).bit_length()+1) == n.bit_length() else n+(1<<m) # Chai Wah Wu, Jul 06 2022

Crossrefs

Cf. A007814.

Sequence in context: A155790 A200646 A198130 * A241388 A305574 A248259

Adjacent sequences: A309770 A309771 A309772 * A309774 A309775 A309776

Keyword

nonn

Author

Rémy Sigrist, Aug 16 2019

Status

approved