A382357 Lexicographically earliest sequence of distinct positive integers such that the 2-adic valuations of adjacent terms differ exactly by one.

1, 2, 3, 6, 4, 8, 12, 10, 5, 14, 7, 18, 9, 22, 11, 26, 13, 30, 15, 34, 17, 38, 19, 42, 20, 24, 16, 32, 48, 40, 28, 46, 21, 50, 23, 54, 25, 58, 27, 62, 29, 66, 31, 70, 33, 74, 35, 78, 36, 56, 44, 72, 52, 82, 37, 86, 39, 90, 41, 94, 43, 98, 45, 102, 47, 106, 49

Offset: 1

Author

Rémy Sigrist, Mar 22 2025

Keywords

• nonn
• base

Comments

The first term with a given 2-adic valuation, say k, is necessarily 2^k.

Empirically, powers of two appear as pairs of consecutive terms.

We cannot have three consecutive powers of 2: if a(n) = 2^k and a(n+1) = 2^(k+1) then a(n+2) <= 3*2^k < 2^(k+2).

All powers of two appear in the sequence:

- by contradiction: if 2^m is missing, then the 2-adic valuation of the terms of the sequence is bounded by m,

- by necessity, we have some k < m such that all the integers with 2-adic valuation k appear in the sequence,

- hence all integers with 2-adic valuation k+1 (and k-1 provided k > 0) will appear in the sequence,

- gradually, all integers with 2-adic valuation k+2, k+3, etc. and eventually 2^m, will appear, a contradiction.

Conjecture: this sequence is a permutation of the positive integers.

The fact that A007814 contains every positive integer infinitely many times is not sufficient to guarantee that the present sequence is a permutation of the positive integers (the variant based on A003602 instead of A007814 contains only finitely many even numbers, and so is not a permutation of the positive integers, although A003602 contains every positive integer infinitely many times).

Examples

			The initial terms are:
  n   a(n)  A007814(a(n))
  --  ----  -------------
   1     1              0
   2     2              1
   3     3              0
   4     6              1
   5     4              2
   6     8              3
   7    12              2
   8    10              1
   9     5              0
  10    14              1
  11     7              0
  12    18              1
  13     9              0
  14    22              1
  15    11              0
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Rémy Sigrist, Colored scatterplot of the first million terms (blue pixels for even n's, red pixels for odd n's)
• Rémy Sigrist, PARI program

Crossrefs

Cf. A003602, A007814, A073675, A266089, A382360.

Programs

PARI

\\ See Links section.