cp's OEIS Frontend

A085635 Compute S, the number of different quadratic residues modulo B for every base B. If the density S/B is smaller for B than for every B' less than B, then B is added to the sequence.

%I A085635 #37 Oct 14 2023 23:43:17
%S A085635 1,3,4,8,12,16,32,48,80,96,112,144,240,288,336,480,560,576,720,1008,
%T A085635 1440,1680,2016,2640,2880,3600,4032,5040,7920,9360,10080,15840,18480,
%U A085635 20160,25200,31680,37440,39600,44352,50400,55440,65520,85680,95760
%N A085635 Compute S, the number of different quadratic residues modulo B for every base B. If the density S/B is smaller for B than for every B' less than B, then B is added to the sequence.
%C A085635 After 2880, 3360 has exactly the same density (5%).
%H A085635 Keith F. Lynch, <a href="/A085635/b085635.txt">Table of n, a(n) for n = 1..200</a> (terms 1..111 from Hugo Pfoertner)
%H A085635 Andreas Enge, William Hart, Fredrik Johansson, <a href="http://arxiv.org/abs/1608.06810">Short addition sequences for theta functions</a>, arXiv:1608.06810 [math.NT], 2016-2018.
%e A085635 a(3)=4 because for B=4 the different quadratic residues are {0,1}, so S=2, the density is D_4=50%, which is smaller than D_2=100% and D_3=66.67%.
%t A085635 Block[{s = Range[0, 2^14 + 1]^2, t}, t = Array[#/Length@ Union@ Mod[Take[s, # + 1], #] &, Length@ s - 1]; Map[FirstPosition[t, #][[1]] &, Union@ FoldList[Max, t]]] (* _Michael De Vlieger_, Sep 10 2018 *)
%o A085635 (PARI) r=-1;for(n=1,1e6,t=1-sum(k=1,n,issquare(Mod(k,n)))/n;if(t>r,r=t;print1(n", "))) \\ _Charles R Greathouse IV_, Jul 15 2011
%o A085635 (PARI) sq1(m)=sum(n=0,m-1,issquare(Mod(n,m)))
%o A085635 sq(n,f=factor(n))=prod(i=1,#f~,my(p=f[i,1],e=f[i,2]); if(e>1,sq1(p^e),p\2+1))
%o A085635 r=2;for(n=1,1e6, t=sq(n)/n; if(t<r, r=t; print1(n", "))) \\ _Charles R Greathouse IV_, Mar 30 2018
%Y A085635 Cf. A000224, A084848.
%K A085635 nonn
%O A085635 1,2
%A A085635 Jose R. Brox (tautocrona(AT)terra.es), Jul 10 2003
%E A085635 More terms from _Jud McCranie_, Jul 12 2003
%E A085635 a(1) and PARI programs corrected by _Hugo Pfoertner_, Aug 23 2018