A374717 For n a power of 2, a(n) = n. Otherwise let k = n - 2^j (> 0) where 2^j is the greatest power of 2 not exceeding n, then a(n) = least novel m*a(k); m a term in A033844.
1, 2, 3, 4, 7, 6, 9, 8, 19, 14, 21, 12, 49, 18, 27, 16, 53, 38, 57, 28, 133, 42, 63, 24, 361, 98, 147, 36, 343, 54, 81, 32, 131, 106, 159, 76, 371, 114, 171, 56, 1007, 266, 399, 84, 931, 126, 189, 48, 2809, 722, 1083, 196, 2527, 294, 441, 72, 6859, 686, 1029, 108, 2401, 162, 243, 64, 311
Offset: 1
Examples
a(1) = 1, a(2) = 2 because both are powers of 2. a(3) = 3 since for n = 3, k = 1, a(1) = 1 and m = 3. a(4) = 4 because 4 is a power of 2
For a(5), k = 1, a(1) = 1 and therefore a(5) = 1*7 since 7 is least term in A033844 not already used.
Whereas the Name defines each individual term recursively, the following procedure describes a recursion for generating the first 2^k terms from the first 2^(k-1) terms: Let S(0) = {1}, and then S(k) = {2*S(k-1), S(k-1)}, where 2*S(k-1) means twice every term in S(k-1). Thus from
S(0) = {1} we obtain:
S(1) = {2,1},
S(2) = {4,2,2,1},
S(3) = {8,4,4,2,4,2,2,1},
S(4) = {16,8,8,4,8,4,4,2,8,4,4,2,4,2,2,1} etc.
Convert these (indices) to primes as follows:
P(0) = {2},
P(1) = {3,2},
P(2) = {7,3,3,2},
P(3) = {19,7,7,3,7,3,3,2},
P(4) = {53,19,19,7,19,7,7,3,19,7,7,3,7,3,3,2}, etc.
Set U(0) = 1 and U(k) = U(k-1)*P(k-1) prepended by U(k-1), thus:
U(0) = {1},
U(1) = {1,2},
U(2) = {1,2,3,4},
U(3) = {1,2,3,4,7,6,9,8},
U(4) = {1,2,3,4,7,6,9,8,19,14,21,12,49,18,27,16}, etc.
Thus U(k) gives the first 2^k terms of the sequence because the primes in P(k) are the greatest prime factors of the corresponding terms.
From _Michael De Vlieger_, Aug 09 2024: (Start)
Using the alternative binary definition:
For n = 9, n-1 = 1000_2; c_3 = 1, hence a(9) = prime(2^3)^1 = 19.
For n = 10, n-1 = 1001_2; c_0 = 1, c_2 = 1; a(10) = prime(2^0)^1 * prime(2^2)^1 = 2*7 = 14.
For n = 11, n-1 = 1010_2; c_1 = 1, c_2 = 1; a(11) = prime(2^1)^1 * prime(2^2)^1 = 3*7 = 21.
For n = 12, n-1 = 1011_2; c_0 = 2, c_1 = 1; a(12) = prime(2^0)^2 * prime(2^1)^1 = 2^2*3 = 12.
For n = 13, n-1 = 1100_2; c_2 = 2; a(13) = prime(2^2)^2 = 7^2 = 49.
For n = 2^k + 2^(k-1) = 3*2^(k-1), n-1 = 2^(k+1) - 2^(k-1) - 1.
c_0 = k-1, c_1 = 1, therefore we have fixed point a(3*2^(k-1)) = 3*2^(k-1). (End)
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^14, showing primes in red, perfect prime powers in gold, squarefree composites in green, and with blue and purple representing numbers neither squarefree nor prime powers, where purple represents powerful numbers that are not prime powers.
- Michael De Vlieger, Fan style binary tree showing a(n), n = 1..8192 using essentially the same color function as immediately above, with exception that composite primorials appear in bright green.
Programs
-
Mathematica
Block[{a, c, k, m, t, nn}, nn = 2^7; c[_] = False; Do[Set[{m, k}, {1, n - 2^Floor[Log2[n]]}]; If[k == 0, Set[{a[n], c[n]}, {n, True}], While[Set[t, Prime[2^m] a[k]]; c[t], m++]; Set[{a[n], c[t]}, {t, True}]], {n, nn}]; Array[a, nn] ] (* Michael De Vlieger, Aug 06 2024 *)
Formula
a(2^k) = 2^k, a(3*2^k) = 3*2^k.
a(2^k-1) = 3^(k-1), k >= 1; a(2^k+1) = A033844(k+1); k >= 0.
Comments