A099501 Least number of members in a subset of integers in the interval [n^2+1, (n+1)^2-1] whose product is twice a square.

1, 1, 3, 1, 1, 2, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2

Offset

1,3

Comments

Granville and Selfridge conjecture that a(n) <= 3 for all n.

Links

Giovanni Resta, Table of n, a(n) for n = 1..10000

Andrew Granville and John Selfridge, Product of integers in an interval, modulo squares, Electronic Journal of Combinatorics, Volume 8(1), 2001.

Example

a(5) = 1 because the interval [26,35] contains two sets of such integers ({32} and {27,28,30,35}) and the smallest set has 1 member.

Mathematica

Needs["DiscreteMath`Combinatorica`"]; Table[lst=Range[n^2+1, (n+1)^2-1]; x=Times@@lst; {p, e}=Transpose[FactorInteger[x]]; Do[If[e[[i]]==1 && p[[i]]!=2, lst=DeleteCases[lst, _?(Mod[ #, p[[i]]]==0&)]], {i, Length[p]}]; k=1; found=False; While[ !found && k<=Length[lst], m=0; While[ !found && m<Binomial[Length[lst], k], ss=UnrankKSubset[m, k, lst]; x=Times@@ss; If[Mod[x, 2]==0 && IntegerQ[Sqrt[x/2]], found=True]; m++ ]; k++ ]; (*Print[{n, ss, x}]; *)Length[ss], {n, 150}]

Crossrefs

Cf. A099500 (number of subsets), A099502 (n such that a(n)=3).

Sequence in context: A285770 A370892 A174820 * A089762 A257567 A318440

Adjacent sequences: A099498 A099499 A099500 * A099502 A099503 A099504

Keyword

nonn

Author

T. D. Noe, Oct 20 2004

Status

approved