|
%I #70 Apr 03 2022 09:57:37
%S 2,3,2,2,9,2,2,15,2,2,15,2,32,81,2,2,55,21,2,39,2,2,4141,2,18,51,2,
%T 551,39,2,2,21267,21,2,1012,2,2,826,330,2,729,2,136,204,2,3,280,20,2
%N Least k > 1 such that all divisors d of (k^(2n+1)+1)/(k+1) satisfy d == 1 (mod 2n+1).
%C a(n) is the smallest k > 1 such that Phi_m(-k) has all its divisors == 1 (mod n) for all m > 1 dividing 2n+1, where Phi_m(x) are the cyclotomic polynomials.
%C By Schinzel's hypothesis H, a(n) exists for every n (see A298076).
%C If 2n+1 is a prime > 3, then a(n) = 2.
%C We have a(n)^(2n+1) == a(n) (mod 2n+1), so every composite number 2n+1 is a weak Fermat pseudoprime to base a(n).
%C a(n) >= A239452(2n+1).
%C a(42) requires factorization of a 132 digit composite. - _M. F. Hasler_, Oct 16 2018
%C From _Kevin P. Thompson_, Mar 30 2022: (Start)
%C Additional nontrivial terms: a(55) = 111, a(61) = 165, a(64) = 216, a(66) = 49.
%C a(49) >= 656811 (a C322 remains to be factored to verify k=656811).
%C a(52) >= 3547020 (a C288 remains to be factored to verify k=3547020).
%C a(57) >= 4900 (a C258 remains to be factored to verify k=4900).
%C a(58) > 784720.
%C a(59) >= 714 (a C299 remains to be factored to verify k=714).
%C a(60) >= 233 (a C240 remains to be factored to verify k=233).
%C a(62) >= 126 (a C191 remains to be factored to verify k=126). (End)
%H Kevin P. Thompson, <a href="/A298310/a298310_1.txt">Factorizations to support known terms of a(n) for n = 1..68</a>
%F a(n) = min{k > 1: for all prime p, if p | (k^(2n+1)+1)/(k+1) then p == 1 (mod 2n+1)}. - _Kevin P. Thompson_, Mar 18 2022
%e a(170) = 2 wherein 2*170 + 1 = 341 = 11*31 is the smallest psp(2).
%e From _M. F. Hasler_, Oct 15 2018: (Start)
%e a(0) = 2 is the least integer k > 1 for which (k+1)/(k+1) == 1 (mod 1). (Here we even have equality, but any integer is congruent to any other integer, modulo 1.)
%e a(1) = 3 is the least k > 1 for which (k^3+1)/(k+1) = k^2 - k + 1 = P3(-k) == 1 (mod 3). Indeed, P3(-3) = 7 == 1 (mod 3), while P3(-2) = 3 == 0 (mod 3). (End)
%t Table[SelectFirst[Range[2, 100], AllTrue[Divisors[(#^(2 n + 1) + 1)/(# + 1)], Mod[#, 2 n + 1] == 1 &] &], {n, 21}] (* _Michael De Vlieger_, Feb 01 2018 *)
%o (PARI) isok(k, n) = {fordiv((k^(2*n+1)+1)/(k+1), d, if (Mod(d, (2*n+1)) != 1, return (0));); return(1);}
%o a(n) = {my(k = 2); while (!isok(k, n), k++); k;} \\ _Michel Marcus_, Jan 19 2018
%o (PARI) A298310(n)={n=n*2+1;for(k=2,oo,fordiv(n,m,m>1&&vecmax(factor(polcyclo(m,-k))[,1]%n)!=1&& next(2));return(k))} \\ _M. F. Hasler_, Oct 14 2018
%Y Cf. A239452, A298076 (see Ordowski's conjecture for b < -1 and odd n).
%K nonn,hard,more
%O 0,1
%A _Thomas Ordowski_ and _Krzysztof Ziemak_, Jan 17 2018
%E a(22) corrected by _Robert Israel_, Jan 18 2018
%E a(1) corrected by _Michel Marcus_, Jan 19 2018
%E a(27)-a(30) from _Robert Price_, Feb 17 2018
%E a(31)-a(41) from _M. F. Hasler_, Oct 15 2018
%E a(42)-a(48) from _Kevin P. Thompson_, Mar 18 2022
|
