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,2

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.

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.

Formula

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

Example

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.

Mathematica

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

Crossrefs

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

Sequence in context: A136336 A244456 A232394 * A115178 A331934 A049885

Adjacent sequences: A356623 A356624 A356625 * A356627 A356628 A356629

Keyword

nonn

Author

Michael De Vlieger, Aug 24 2022

Status

approved