cp's OEIS Frontend

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

%I A356626 #9 Sep 08 2022 01:35:05
%S A356626 1,2,4,7,15,29,61,125,249,497,1009,2033,4081,8177,16369,32753,65521,
%T A356626 131057,262081,524225,1048513,2097089,4194241,8388545,16777153,
%U A356626 33553921,67108353,134217217,268434945,536870401,1073741313,2147483137,4294966785,8589934081,17179868673
%N A356626 Position of A332979(n) in the Doudna sequence A005940.
%C A356626 Offset to match A332979.
%C A356626 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.
%C A356626 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.
%C A356626 Theorem 1: the maximum of s(n) for n = 2^(k-1)+1..2^k is a prime power.
%C A356626 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.
%C A356626 Theorem 2: s(2^k-2^j+1) = prime(j+1)^(k-j), j=1..k-1.
%C A356626 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.
%C A356626 The maximum of s(n) for n = 2^(k-1)+1..2^k is tantamount to the maximum of row k of A180944.
%H A356626 Michael De Vlieger, <a href="/A356626/b356626.txt">Table of n, a(n) for n = 0..3321</a>
%H A356626 Michael De Vlieger, <a href="https://oeis.org/A332979/a332979_3.png">Fan style binary tree</a> showing row m = 2..15 of A005940, highlighting A332979(m-1) in red.
%F A356626 a(0) = 1; a(n) = 2^n - 2^(pi(p)-1) + 1 for A332979(n) = p^e and n>1.
%e A356626 A332979(3) = 9 = 3^2, therefore a(3) = 2^3-2^(pi(3)-1)+1 = 2^3-2^1+1 = 8-2+1 = 7.
%e A356626 A332979(8) = 16807 = 7^5, therefore a(8) = 2^8-2^(pi(7)-1)+1 = 2^8-2^3+1 = 249.
%t A356626 {1}~Join~Table[2^n - 2^(# - 1) + 1 &[FirstPosition[#, Max[#]][[1]]] &@ Thread[Power[Prime[#], Reverse[#] ] ] &@ Range[n], {n, 34}]
%Y A356626 Cf. A000120, A000961, A005940, A006530, A023416, A023758, A180944, A332979.
%K A356626 nonn
%O A356626 0,2
%A A356626 _Michael De Vlieger_, Aug 24 2022