|
%I #10 Feb 07 2024 09:01:16
%S 1,1,1,1,2,1,2,4,2,4,4,4,8,4,32,8,16,16,32,16,32,128,32,64,59,124,499,
%T 32,478,122,248,1886,239,1980,240,944,500,6181,3848,970,3776,3844,
%U 6167,13774,3806,27985,24562,4016,102193,13224,105671,12565,399445,29436
%N Number of distinct products of subsets of integers in the interval [n^2+1, (n+1)^2-1] which are twice a square.
%C Granville and Selfridge prove Kaplansky's conjecture that a(n) > 0 for all n. Interestingly, the first 24 terms are powers of 2, but the 25th term is not.
%C a(n) <= A120253(n) = 2^A120254(n). The sequences are equal iff each subset has a distinct product. - _Martin Fuller_, Jun 13 2006
%H Andrew Granville and John Selfridge, <a href="https://doi.org/10.37236/1549">Product of integers in an interval, modulo squares</a>, Electronic Journal of Combinatorics, Volume 8(1), 2001.
%e a(5) = 2 because the interval [26,35] contains two sets of such integers: {32} and {27,28,30,35}.
%e a(25) < A120253(25) because there are distinct subsets with the same product. The smallest is 627*630*646*648*650*660*663*672 = 627*637*640*646*648*660*663*675 = 2*125707982400^2.
%t 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]}]; i=1; cnt=0; xLst={}; While[i<2^Length[lst], ss=NthSubset[i, lst]; x=Times@@ss; If[Mod[x, 2]==0 && IntegerQ[Sqrt[x/2]] && !MemberQ[xLst, x], cnt++; AppendTo[xLst, x] (*; Print[{n, ss}]*)]; i++ ]; cnt, {n, 31}]
%Y Cf. A099501 (size of the subset having the least number of integers).
%Y Cf. A120253 number of subsets whose product is twice a square.
%K nonn
%O 1,5
%A _T. D. Noe_, Oct 20 2004
%E More terms from _Martin Fuller_, Jun 13 2006
|
