A137576 a(n) = A002326(n) * A006694(n) + 1.

1, 3, 5, 7, 13, 11, 13, 17, 17, 19, 31, 23, 41, 55, 29, 31, 41, 61, 37, 49, 41, 43, 85, 47, 85, 57, 53, 81, 73, 59, 61, 73, 73, 67, 111, 71, 73, 141, 151, 79, 217, 83, 89, 113, 89, 109, 131, 145, 97, 211, 101, 103, 169, 107, 109, 145, 113, 221, 133, 193, 221, 141, 301, 127

Offset: 0

Author

Vladimir Shevelev, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008

Keywords

• nonn

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_1A002326((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.

Crossrefs

Cf. A002326, A006694, A138193, A138217, A138227, A141232, A195468.

Programs

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 *)

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

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

Extensions

Edited and extended by Ray Chandler, May 08 2008