A356626 Position of A332979(n) in the Doudna sequence A005940.

1, 2, 4, 7, 15, 29, 61, 125, 249, 497, 1009, 2033, 4081, 8177, 16369, 32753, 65521, 131057, 262081, 524225, 1048513, 2097089, 4194241, 8388545, 16777153, 33553921, 67108353, 134217217, 268434945, 536870401, 1073741313, 2147483137, 4294966785, 8589934081, 17179868673

Offset: 0

Author

Michael De Vlieger, Aug 24 2022

Keywords

• nonn

Comments

Offset to match A332979.

Let n_2 be the binary expansion of n with a length of b bits. Let W(n) = A000120(n) the binary weight of n, i.e., the number of ones in n_2, while Z(n) = b - W(n) be the number of zeros in n_2. Let Q be the number of runs of ones in n_2, L(k) be the run length of the k-th least significant run of ones, and P(k) the partial sum of the number of zeros to the right of the k-th run of ones.

Define the Doudna function f(n) = Product_{k=1..Q} prime(P(k)+1)^L(k). The Doudna sequence A005940(n) = s(n) = f(n-1) with s(1) = 1.

Theorem 1: the maximum of s(n) for n = 2^(k-1)+1..2^k is a prime power.

Proof. s(n) corresponds to f(m), m = n-1, hence m = 2^(k-1)..2^k. The number m in this domain has k bits. Binary numbers involve zeros and ones, thus, k = W(m) + Z(m). It is clear that W(m) = Omega(f(m)) and Z(m) = pi(gpf(f(m)))-1. Hence we have k = Omega(f(m)) + pi(gpf(f(m)))-1. We maximize f(m) for a k-bit number m when the greatest prime factor of f(m) has maximum multiplicity, therefore the maximum of s(n) for n = 2^(k-1)+1..2^k is a prime power.

Theorem 2: s(2^k-2^j+1) = prime(j+1)^(k-j), j=1..k-1.

Proof: We write (2^k-2^j)_2 as (k-j) ones followed by j zeros, a k-bit binary number. We have Q=1 run of ones in (2^k-2^j)_2. Therefore f(2^k-2^j) = prime(P(1)+1)^L(1) = prime(j+1)^(k-j), that is, row k of A180944.

The maximum of s(n) for n = 2^(k-1)+1..2^k is tantamount to the maximum of row k of A180944.

Examples

			A332979(3) = 9 = 3^2, therefore a(3) = 2^3-2^(pi(3)-1)+1 = 2^3-2^1+1 = 8-2+1 = 7.
A332979(8) = 16807 = 7^5, therefore a(8) = 2^8-2^(pi(7)-1)+1 = 2^8-2^3+1 = 249.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..3321
• Michael De Vlieger, Fan style binary tree showing row m = 2..15 of A005940, highlighting A332979(m-1) in red.

Crossrefs

Cf. A000120, A000961, A005940, A006530, A023416, A023758, A180944, A332979.

Programs

Mathematica

{1}~Join~Table[2^n - 2^(# - 1) + 1 &[FirstPosition[#, Max[#]][[1]]] &@ Thread[Power[Prime[#], Reverse[#] ] ] &@ Range[n], {n, 34}]

Formula

a(0) = 1; a(n) = 2^n - 2^(pi(p)-1) + 1 for A332979(n) = p^e and n>1.