A365436 - OEIS

A365436

a(2^k) = 2^k for all k >= 0. let 2^r be the smallest power of 2 which exceeds n, then a(n) = the least novel m*a(k), where k = 2^r-n, and m is not a prior term.

1, 2, 3, 4, 15, 10, 5, 8, 30, 60, 90, 24, 18, 12, 6, 16, 42, 84, 126, 168, 630, 420, 210, 56, 35, 70, 105, 28, 21, 14, 7, 32, 63, 154, 189, 252, 945, 770, 315, 504, 1890, 3780, 5670, 1512, 1134, 756, 378, 144, 54, 108, 162, 216, 810, 540, 270, 72, 45, 110, 135

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Based on a recursion similar to that which produces the Doudna sequence, A005940, (using the least power of 2 exceeding n rather than the greatest power of 2 not exceeding n). All 2^(n-1) terms between between fixed points 2^n and 2^(n+1) are multiples m*a(k) of m, the least unused term, and m is a(2^(k+1)-1).

Conjectured to be a permutation of the positive integers.

From David A. Corneth, Nov 11 2023: (Start)

This is a permutation of the positive integers.

To prove this we'll show that each integer occurs at most once and at least once hence exactly once.

By definition (...a(n) = the least novel...) each positive integer occurs at most once.

Now suppose t is the smallest term not in the sequence. Then there exists u such that a(1)..a(u) contain the positive integers from 1 through t-1. Then a(i) = t for some 1 <= i <= 2^e - 1 where 2^e - 1 >= u. If a(i) != t for 1 <= i <= 2^e-2 then a(2^e - 1) = t as then k = 1, a(k) = 1 and m is not a prior term (t did not occur earlier).

Hence t occurs at least once. As it also occurs at most once every positive integer occurs exactly once and this sequence is a permutation of the positive integers. (End)

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^12, showing primes in red, composite prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue.

Michael De Vlieger, Fan style binary tree of a(n), n = 1..8191, showing primes in red, squares of primes in orange, other composite prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue, purple (also in A286708), and pink (also in A303606).

Index entries for sequences that are permutations of the natural numbers

EXAMPLE

a(3) = 3 since k = 1, a(1) = 1 and 3 is the smallest number which is not already a term.

a(5) = 15 since k = 8-5 = 3, a(3) = 3 and 5 is the smallest number which is not already a term.

a(31) = 7, the least unused term at this point in the sequence.

MATHEMATICA

nn = 120; c[_] := False; c[1] = True; m[_] := 1; a[1] = 1; c[1] = True;

Do[If[IntegerQ[#],

Set[k, i],

While[Or[c[m[#]], c[Set[k, # m[#]]]], m[#]++] &[

a[2^Floor[# + 1] - i]]] &@ Log2[i];

Set[{a[i], c[k]}, {k, True}], {i, nn}];