|
%I #17 Nov 15 2019 09:24:07
%S 2,3,12,21,60,184,280,364,1456,3124,5236,17185,25249,49504,233776,
%T 364144,775369,3864169,8794864,10869664,32384209,105361344,173899609,
%U 425088976,2140195264,2805544681,10310263441,11940537961,38432362081,43395268849,51802119889,299530084681
%N Numbers with ever-increasing minimal-square-deniers.
%C The Jacobi of modular reductions of a number is often used by a bignum library to give a quick (negative) answer to the question of whether an integer is an exact square. This sequence gives the cutoffs for ever-increasing numbers of required modular tests, on the assumption that one is avoiding a brute force square-root/square/compare. All terms to 8794864 found by Jack Brennen.
%H J. Brennen, discussion about <a href="http://groups.yahoo.com/group/primenumbers/message/4801">issquare() tests without use of sqrt()</a> on Caldwell's 'primenumbers' list.
%H Jack Brennen and others, <a href="/A066730/a066730.txt">Programming Question - detecting squareness</a>, digest of 32 messages in primenumbers Yahoo group, in particular message 8, Jan 15 - Jan 22, 2002.
%e 2 is 'square-denied' by 3, as 2 is not a quadratic residue mod 3 3 is square-denied by 2^2=4, but not by any lower prime power (2 or 3) 12 has 5 as its minimal square-denier (0 mod 2, 0 mod 3, 0 mod 4 all QRs) 21 has 2^3=8 as its minimal square-denier. (note that 24 has 7 as its minimal square-denier, the first number with that property, but it is larger than 21)
%t mo = Select[Range[3, 60], Length[FactorInteger[#]] == 1 &]; T = Table[0 Range[mo[[i]]], {i, Length@ mo}]; Do[T[[i, 1 + Mod[j^2, mo[[i]]]]] = 1, {i, Length@mo}, {j, mo[[i]]}]; w[n_] := If[IntegerQ@ Sqrt@ n, -1, Block[{k=1}, While[k < Length[mo] && T[[k, 1 + Mod[n, mo[[k]]]]] == 1, k++]; k-1]]; rec = -1; n = 1; L = {}; While[n < 8 10^5, n++; v = w[n]; If[v > rec, rec = v; AppendTo[L, n]]]; L (* computes first 17 terms, _Giovanni Resta_, Nov 15 2019 *)
%K nonn
%O 1,1
%A _Phil Carmody_, Jan 15 2002
%E Offset set to 1 and terms a(20)-a(32) added by _Giovanni Resta_, Nov 15 2019
|
