A359416 Write n as 2^m - k, where 2^m is the least power of 2 >= n (0 <= k <= 2^(m-1)-1). For n a power of 2 (k = 0), a(n) = n. For numbers with k > 0, a(n) is the least p*a(k) which has not occurred previously, the count of k being taken from right to left (backwards) from k = 1 at 2^m - 1.

1, 2, 3, 4, 9, 6, 5, 8, 25, 18, 27, 12, 15, 10, 7, 16, 49, 50, 105, 36, 81, 54, 75, 24, 35, 30, 45, 20, 21, 14, 11, 32, 121, 98, 231, 100, 495, 210, 175, 72, 225, 162, 243, 108, 315, 150, 147, 48, 77, 70, 165, 60, 135, 90, 125, 40, 55, 42, 63, 28, 33, 22, 13, 64

Offset: 1

Author

David James Sycamore, Dec 30 2022

Keywords

• nonn

Comments

A variant of the recursive definition of the Doudna sequence A005940, and A356886. Whereas a sequence is normally computed in natural order (A000027) of its indices (a(1), a(2), a(3), etc.), in this case terms with indices n other than powers of 2 are computed backwards, right to left from the least power of 2 exceeding n (ordering as in A122155). For example, with terms between a(4) and a(8) the order of computation is a(7), then a(6), then a(5), each time choosing a least novel number matching the definition, see Example. Compare with similar sequence A356886, where a similar definition is used but the count is conventional: left to right.

Conjectured to be a permutation of the positive integers in which primes appear in natural order. The even bisection, when divided by 2, reproduces the sequence.

Examples

			a(3) = 3 because 3 = 2^2 - 1, so k = 1 and 3 is the least odd prime multiple of a(1).
a(7) = 5 because 7 = 2^3 - 1, k = 1, a(1) = 1 and 5 is the least multiple of 1 not seen already. (At this point a(5), a(6) have not been found.)
a(6) = 6 since k = 2, a(2) = 2, and 3*2 is the least number not seen already.
a(5) = 9 since k = 3, a(3) = 3, so we choose 3*3.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16384
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^12.
• Michael De Vlieger, Labeled fan-style binary tree showing a(n), n = 1..2^12 in levels k such that n = 2^k+1..2^(k+1), with a color function indicating a(2^k) and a(n), where a(n) = a(2^k) in green, a(n) < a(2^k) in blues, and a(n) > a(2^k) in yellows, oranges, and reds.

Crossrefs

Cf. A000027, A005940, A122155, A356886, A357057.

Programs

Mathematica

nn = 2^6; c[] = False; Do[Set[{m, k}, {2, n - 2^Floor[Log2[n]]}]; If[k == 0, Set[{a[n], c[n]}, {n, True}], While[Set[t, Prime[m] a[k]]; c[t], m++]; Set[{a[2^#/(1 + Boole[IntegerQ[Log2[n]]]) - n + 2^(# - 1) &@ IntegerLength[n, 2]], c[t]}, {t, True}]], {n, 2^Ceiling[Log2[nn]] }]; Array[a, nn] (* _Michael De Vlieger, Jan 02 2023 *)

Formula

a(2*n)/2 = a(n); n >= 1.

a(2^n - 1) = prime(n); n >= 2.

a(2^n + 1) = prime(n)^2; n >= 2.

At the occurrence of 2^n (n >= 3) the following pattern of five successive terms is observed: 3*prime(n-1), 2*prime(n-1), prime(n), 2^n, prime(n)^2, ....

For n >= 2, a(2^n + 1)/a(2^n - 1) = prime(n); compare with A357057).