OFFSET
0,2
COMMENTS
Composite numbers n for which a((n-1)/2)=n are called overpseudoprimes to base 2 (A141232).
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.
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).
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.
LINKS
Ray Chandler, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, Exact exponent of remainder term of Gelfond's digit theorem in binary case, arXiv:0804.3682 [math.NT], 2008.
Vladimir Shevelev, Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithmetica 136 (2009), 91-100.
FORMULA
It can be shown that if p is an odd prime then a((p^k-1)/2)=1+k*phi(p^k).
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
MATHEMATICA
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008
EXTENSIONS
Edited and extended by Ray Chandler, May 08 2008
STATUS
approved