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.

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

Author

David James Sycamore, Apr 15 2024

Keywords

• nonn

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.

Examples

			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.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16384
• 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.
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A000027, A005940, A052330, A269848, A368900.

Programs

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 *)

PARI

\\ See PARI link

Formula

a(2^k + 1) = prime(k+1).