cp's OEIS Frontend

A219610 Number of ways n can be written as sum of squares < n.

%I A219610 #24 Apr 28 2022 05:31:14
%S A219610 1,0,1,1,1,2,2,2,3,3,4,4,5,6,6,6,7,9,10,10,12,13,14,14,16,18,20,21,23,
%T A219610 26,27,28,31,34,37,38,42,46,49,50,55,60,63,66,71,78,81,84,90,97,104,
%U A219610 107,116,124,132,135,144,154,163,169,178,192,201,209,219,235,247,256,271,286,302,311,329,347,365,378,397,420,438,455,476,503
%N A219610 Number of ways n can be written as sum of squares < n.
%C A219610 Inspired by A034295, but not involving the same geometrical idea & restrictions.
%H A219610 Alois P. Heinz, <a href="/A219610/b219610.txt">Table of n, a(n) for n = 0..10000</a>
%F A219610 a(n^2+1) >= A034295(n).
%e A219610 a(16)=7 since 16 = 3^2+7*1 = 3^2+2^2+3*1 = 2^2+12*1 = 2*2^2+8*1 = 3*2^2+4*1 = 4*2^2 = 16*1^2 (where 1 = 1^2).
%e A219610 a(17)=9 since 17 = 4^2+1 = 3^2+8*1 = 3^2+2^2+4*1 = 3^2+2*2^2 = 2^2+13*1 = 2*2^2+9*1 = 3*2^2+5*1 = 4*2^2+1 = 17*1^2.
%p A219610 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A219610       `if`(i<1, 0, b(n, i-1) +`if`(i^2>n, 0, b(n-i^2, i))))
%p A219610     end:
%p A219610 a:= proc(n) local r; r:= isqrt(n);
%p A219610        b(n, r-`if`(r^2>=n, 1, 0))
%p A219610     end:
%p A219610 seq(a(n), n=0..100);  # _Alois P. Heinz_, Apr 16 2013
%t A219610 b[n_, i_] := b[n, i] = If[n == 0, 1,
%t A219610      If[i < 1, 0, b[n, i - 1] + If[i^2 > n, 0, b[n - i^2, i]]]];
%t A219610 a[n_] := With[{r = Floor@Sqrt[n]}, b[n, r - If[r^2 >= n, 1, 0]]];
%t A219610 Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Apr 28 2022, after _Alois P. Heinz_ *)
%o A219610 (PARI) a(n,m)={!m && n<5 && return(n!=1); m || m=sqrtint(n-1); sum(k=2,m, sum(j=1,n\k^2,a(n-j*k^2,k-1)),1)}
%Y A219610 Cf. A034295.
%K A219610 nonn
%O A219610 0,6
%A A219610 _M. F. Hasler_, Apr 12 2013