%I #30 Nov 14 2021 01:08:15
%S 1,3,5,7,13,11,13,17,17,19,31,23,41,55,29,31,41,61,37,49,41,43,85,47,
%T 85,57,53,81,73,59,61,73,73,67,111,71,73,141,151,79,217,83,89,113,89,
%U 109,131,145,97,211,101,103,169,107,109,145,113,221,133,193,221,141,301,127
%N a(n) = A002326(n) * A006694(n) + 1.
%C Composite numbers n for which a((n-1)/2)=n are called overpseudoprimes to base 2 (A141232).
%C Theorem. If p and q are odd primes then the equality a((pq-1)/2)=pq is valid if and only if A002326((p-1)/2)=A002326((q-1)/2). Example: A002326(11) = A002326(44). Since 23 and 89 are primes then a((23*89-1)/2)=23*89.
%C A generalization: If p_1<p_2<...<p_m are distinct odd primes then a(((p_1*p_2*...*p_m)-1)/2)=p_1*p_2*...*p_m if and only if A002326((p_1-1)/2)= A002326((p_2-1)/2)=...=A002326((p_m-1)/2).
%C Moreover, if n is an odd squarefree number and a((n-1)/2)=n then also all divisors d of n satisfy a((d-1)/2)=d and d divides 2^d-2. Thus the sequence of such n is a subsequence of A050217.
%H Ray Chandler, <a href="/A137576/b137576.txt">Table of n, a(n) for n = 0..10000</a>
%H Vladimir Shevelev, <a href="http://arXiv.org/abs/0804.3682">Exact exponent of remainder term of Gelfond's digit theorem in binary case</a>, arXiv:0804.3682 [math.NT], 2008.
%H Vladimir Shevelev, <a href="https://doi.org/10.4064/aa136-1-7">Exact exponent in the remainder term of Gelfond's digit theorem in the binary case</a>, Acta Arithmetica 136 (2009), 91-100.
%F It can be shown that if p is an odd prime then a((p^k-1)/2)=1+k*phi(p^k).
%F a(n) = ord(2,2*n+1) * ((Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1) + 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - _Jianing Song_, Nov 13 2021
%t a[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; Table[a[n], {n, 0, 70}] (* _Jean-François Alcover_, Dec 04 2015, adapted from PARI *)
%o (PARI) a(n)=my(t);sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1 \\ _Charles R Greathouse IV_, Feb 20 2013
%Y Cf. A002326, A006694, A138193, A138217, A138227, A141232, A195468.
%K nonn
%O 0,2
%A _Vladimir Shevelev_, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008
%E Edited and extended by _Ray Chandler_, May 08 2008