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

Author

David James Sycamore, Jul 17 2024

Keywords

• nonn
• changed

Comments

Definition developed from the Doudna recursion A005940, see Example. Conjectured to be a permutation of A318400, numbers whose prime factorization consists only of primes with indices 2^k (terms in A033844).

From David James Sycamore, Aug 09 2024: (Start)

The even bisection when divided by 2 returns the sequence. The odd bisection when transformed by replacing all factors prime(2^k) in a(2*n-1) with prime(2^(k-1)) also returns the sequence (similar to properties of A005940). The sequence is fixed on numbers of the form 2^n or 3*2^n (A029744), since by the definition points at 2^n are already named as such, and if n = 3*2^r then the powers of 2 adjacent to n are 2^r < 2^(r+1) < 3*2^r < 2^(r+2), from which, by the definition we find k = 2^(r+2) - 3*2^r = 2^r(3 - 2) = 2^r, which is a fixed point so a(k) = 2^r, and a(n) is least novel m*a(k); m a term in A033844. Since 2^r is already a term the required m is 3, so a(n) = 3*2^r = n (compare with fixed points of A005940). (End)

Definition analogous to the Name of A005940: Let c_i = number of 1's in binary expansion of n-1 that have i 0's to their right, and let p(j) = j-th prime. Then a(n) = Product_i p(2^i)^c_i. - Michael De Vlieger, Aug 09 2024

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.

Crossrefs

Cf. A005940, A029744, A033844, A318400.

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.