A357601 For n a power of 2, a(n) = n; otherwise, if 2^m is the greatest power of 2 not exceeding n and if k = n-2^m, then a(n) is the smallest number having d(a(k))+1 divisors which has not occurred earlier (d is the divisor counting function A000005).

1, 2, 3, 4, 5, 9, 25, 8, 7, 49, 121, 6, 169, 10, 14, 16, 11, 289, 361, 15, 529, 21, 22, 81, 841, 26, 27, 625, 33, 2401, 14641, 32, 13, 961, 1369, 34, 1681, 35, 38, 28561, 1849, 39, 46, 83521, 51, 130321, 279841, 12, 2209, 55, 57, 707281, 58, 923521, 1874161, 18

Offset

1,2

Comments

Based on a similar recursion to that which produces the Doudna sequence, A005940. Conjectured to be permutation of the positive integers in which the primes appear in natural order.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Michael De Vlieger, Fan style binary tree showing a(n), n = 1..2^13, with a color function representing primes in red, proper prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue and magenta, where the latter also represents powerful numbers that are not prime powers.

Michael De Vlieger, Log log scatterplot of a(n), n = 1..10000, using the same color function as immediately above.

Rémy Sigrist, PARI program

Formula

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

A000005(a(n)) = A063787(n). - Rémy Sigrist, Oct 06 2022

Example

a(9)=7 because k=1, and a(1)=1, which has 1 divisor, so we are looking for the smallest number not yet seen which has 2 divisors. This must be 7 because 2,3,5 have occurred already.

Mathematica

nn = 70; kk = 2^20; c[_] = False; to = Map[DivisorSigma[0, #] &, Range[kk]^2]; t = DivisorSigma[0, Range[kk]]; Do[Set[{m, k}, {1, n - 2^Floor[Log2[n]]}]; If[k == 0, Set[{a[n], c[n]}, {n, True}], d = 1 + DivisorSigma[0, a[k]]; If[OddQ[d], While[Nand[! c[m^2], to[[m]] == d], m++]; Set[{a[n], c[#]}, {#, True}] &[m^2], While[Nand[! c[m], t[[m]] == d], m++]; Set[{a[n], c[m]}, {m, True}]] ], {n, nn}]; Array[a, nn] (* Michael De Vlieger, Oct 05 2022 *)

Prog

(PARI) \\ See Links section.

Crossrefs

Cf. A000005, A005940, A063787.

Sequence in context: A162374 A323289 A355374 * A065885 A274331 A177064

Adjacent sequences: A357598 A357599 A357600 * A357602 A357603 A357604

Keyword

nonn

Author

David James Sycamore, Oct 05 2022

Status

approved