login
A371985
For n a power of 2, a(n) = n. Otherwise a(n) is the smallest novel multiple of a(n - 2^m), where 2^m is the greatest power of 2 not exceeding n.
2
1, 2, 3, 4, 5, 6, 9, 8, 7, 10, 12, 20, 15, 18, 27, 16, 11, 14, 21, 24, 25, 30, 36, 40, 28, 50, 48, 60, 45, 54, 81, 32, 13, 22, 33, 44, 35, 42, 63, 56, 49, 70, 72, 80, 75, 90, 108, 96, 55, 84, 105, 120, 100, 150, 144, 160, 112, 200, 192, 180, 135, 162, 243, 64, 17
OFFSET
1,2
COMMENTS
Reminiscent of the Doudna sequence A005940; also of A052330 and A269848.
All powers of 2 (a(n) = n) are assigned first in order to avoid the second part of the definition giving a(n) = 2^k for some n which is not a power of 2 (see Example for a(12) = 20).
It follows from the definition that all powers of 2, all primes and all multiples of all primes are terms so this sequence is a permutation of the positive integers (A000027), with primes in order.
Each prime power appears before any of its multiples, meaning that this sequence has "property S" as defined in A368900.
LINKS
David A. Corneth, PARI program
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^20.
Michael De Vlieger, Fan style binary tree showing a(n), n = 1..8192, with a color function showing primes in red, perfect prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue or purple. Purple represents powerful numbers that are not prime powers.
FORMULA
a(2^k + 1) = prime(k+1).
EXAMPLE
a(3) = 3, because 2 is the greatest power of 2 not exceeding 3 and 3-2 = 1, so a(3) = 3, the least novel multiple of a(1) = 1.
a(12) is the smallest novel multiple of a(12-8) = a(4) = 4, and at this point in the sequence 4,8,12 are all prior terms and a(16) = 16 is already taken, so a(12) = 20.
MATHEMATICA
nn = 10; c[_] := False; m[_] := 1; a[1] = 1; c[1] = True;
Do[If[i == 0,
k = 2^j + i,
(While[Set[k, m[#] #]; Or[c[k], IntegerQ@ Log2[k]], m[#]++]) &@ a[i]];
Set[{a[2^j + i], c[k]}, {k, True}], {j, nn}, {i, 0, 2^j - 1}];
Array[a, 2^(nn + 1) - 1] (* Michael De Vlieger, Apr 15 2024 *)
PROG
(PARI) \\ See PARI link
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved