

A066730


Numbers with everincreasing minimalsquaredeniers.


2



2, 3, 12, 21, 60, 184, 280, 364, 1456, 3124, 5236, 17185, 25249, 49504, 233776, 364144, 775369, 3864169, 8794864, 10869664, 32384209, 105361344, 173899609, 425088976, 2140195264, 2805544681, 10310263441, 11940537961, 38432362081, 43395268849, 51802119889, 299530084681
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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 everincreasing numbers of required modular tests, on the assumption that one is avoiding a brute force squareroot/square/compare. All terms to 8794864 found by Jack Brennen.


LINKS

Table of n, a(n) for n=1..32.
J. Brennen, discussion about issquare() tests without use of sqrt() on Caldwell's 'primenumbers' list.
Jack Brennen and others, Programming Question  detecting squareness, digest of 32 messages in primenumbers Yahoo group, in particular message 8, Jan 15  Jan 22, 2002.


EXAMPLE

2 is 'squaredenied' by 3, as 2 is not a quadratic residue mod 3 3 is squaredenied by 2^2=4, but not by any lower prime power (2 or 3) 12 has 5 as its minimal squaredenier (0 mod 2, 0 mod 3, 0 mod 4 all QRs) 21 has 2^3=8 as its minimal squaredenier. (note that 24 has 7 as its minimal squaredenier, the first number with that property, but it is larger than 21)


MATHEMATICA

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++]; k1]]; 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 *)


CROSSREFS

Sequence in context: A096632 A124261 A018883 * A077755 A061268 A122604
Adjacent sequences: A066727 A066728 A066729 * A066731 A066732 A066733


KEYWORD

nonn


AUTHOR

Phil Carmody, Jan 15 2002


EXTENSIONS

Offset set to 1 and terms a(20)a(32) added by Giovanni Resta, Nov 15 2019


STATUS

approved



