login
Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).
27

%I #70 Nov 09 2023 08:53:08

%S 2047,3277,4033,8321,65281,80581,85489,88357,104653,130561,220729,

%T 253241,256999,280601,390937,458989,486737,514447,580337,818201,

%U 838861,877099,916327,976873,1016801,1082401,1145257,1194649,1207361,1251949,1252697,1325843

%N Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).

%C Numbers are found by prime factorization of numbers from A001262 and a simple testing of the conditions indicated in comment to A141216.

%C All composite Mersenne numbers (A001348), Fermat numbers (A000215) and squares of Wieferich primes (A001220) are in this sequence. - _Vladimir Shevelev_, Jul 15 2008

%C C. Pomerance proved that this sequence is infinite (see Theorem 4 in the third reference). - _Vladimir Shevelev_, Oct 29 2011

%C Odd composite numbers k such that ord(2,k) * ((Sum_{d|k} phi(d)/ord(2,d)) - 1) = k-1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - _Jianing Song_, Nov 13 2021

%H Amiram Eldar, <a href="/A141232/b141232.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..664 from Michel Marcus)

%H J. H. Castillo, G. García-Pulgarín and J. M. Velásquez-Soto, <a href="http://arxiv.org/abs/1412.5226">q-pseudoprimality: A natural generalization of strong pseudoprimality</a>, arXiv:1412.5226 [math.NT], 2014.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0806.3412">Overpseudoprimes, Mersenne Numbers and Wieferich primes</a>, arXiv:0806.3412 [math.NT], 2008-2012.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0807.2332">Process of "primoverization" of numbers of the form a^n-1</a>, arXiv:0807.2332 [math.NT], 2008.

%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0807.1975">On upper estimate for the overpseudoprime counting function</a>, arXiv:0807.1975 [math.NT], 2008.

%H Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Shevelev/shevelev19.html">Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers</a>, J. Integer Seq. 15 (2012) Article 12.7.7.

%H Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, <a href="http://arxiv.org/abs/1206.0606">Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers</a>, arXiv:1206.0606 [math.NT], 2012.

%F Sum_{n:a(n)<=x} 1 <= x^(3/4)(1+o(1)).

%t A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #]&] - t + 1];

%t okQ[n_] := n > 1 && CompositeQ[n] && n == A137576[(n-1)/2];

%t Reap[For[k = 2, k < 2*10^6, k++, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* _Jean-François Alcover_, Jan 11 2019, from PARI *)

%o (PARI) f(n)=my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576

%o isok(n) = (n>1) && !isprime(n) && (n == f((n-1)/2)); \\ _Michel Marcus_, Oct 05 2018

%Y Cf. A000010, A001262, A141216, A001567, A002326.

%K nonn

%O 1,1

%A _Vladimir Shevelev_, Jun 16 2008

%E Name edited by _Michel Marcus_, Oct 05 2018