need second opinion

[David W. Wilson]

vdmcc wrote:

> hi all,
>             (no, not yet you Neil, wait for it ...) (:-))
>
> I'd like your opinion on a few sequences that look so simple that I fear
> goofing.
> So, be harch if need be.
> ----------------------------------------------------------------------------
> ---
> In a sphere of radius n, at how many different distances from the origin can
> points
> with integer coordinates be found?
> (counting number if "integer shells". Mind you : the distance itself must
> not be integer,
>  the shell only must pass thru an integer point)
> ----------------------------------------------------------------------------
> -----
> I hope I'm right in case of 2 dimensions : circle in x-y plane :
>
>  Table[Length at Union@
>   Flatten at Table[i^2+j^2
> ,{i,0,n},{j,0,Min[i,Floor[Sqrt[n^2-i^2]]]} ],{n,0,64}]
> =
>  {1,2,4,7,10,14,19,24,30,37,44,52,59,69,78,87,98,109,121,133,146,
>     158,173,186,200,216,233,249,265,283,300,318,338,357,377,398,418,439,461,
>     482,505,528,553,576,602,626,653,680,705,735,762,790,819,847,877,904,936,
>     969,1000,1030,1064,1098,1130,1162,1198}
>
> I am sorry, but the terms
> 1,2,4,7,10,14,19,24,30,37,44,52,59,69,78,87,98
> do not match anything in the table : A007980 , A024512 and A022339 give
> partial matches.
> ----------------------------------------------------------------------------
> -----
> 3 dimensional (sphere)
>
>  Table[Length at Union@Flatten at Table[ i^2+j^2+k^2,
> {i,0,n},{j,0,Min[i,Floor[Sqrt[n^2-i^2]]]},
> {k,0,Min[j,Floor[Sqrt[n^2-i^2-j^2]]]}],{n,0,64}]
> =
>   {1,2,5,9,15,23,32,43,55,70,86,103,122,143,166,190,215,243,273,
>
> 304,336,371,406,443,482,523,566,611,656,704,753,803,855,910,966,1024,1083,
>     1145,1207,1270,1336,1404,1474,1544,1616,1690,1766,1843,1922,2004,2086,
>     2170,2256,2344,2434,2524,2616,2711,2807,2905,3003,3104,3206,3310,3415}
>
> I am sorry, but the terms
> 1,2,5,9,15,23,32,43
> do not match anything in the table , A019450 partial match.
> ----------------------------------------------------------------------------
> ------
> 4 dimensional
>
>  Table[Length at Union@Flatten at Table[ i^2+j^2+k^2+l^2,
>       {i,0,n},{j,0,Min[i,Floor[Sqrt[n^2-i^2]]]},
>           {k,0,Min[j,Floor[Sqrt[n^2-i^2-j^2]]]},
>           {l,0,Min[k,Floor[Sqrt[n^2-i^2-j^2-k^2]]]}],  {n,0,64}]
> =
>  {1,2,5,10,17,26,37,50,65,82,101,122,145,170,197,226,257,290,
>     325,362,401,442,485,530,577,626,677,730,785,842,901,962,1025,1090,1157,
>     1226,1297,1370,1445,1522,1601,1682,1765,1850,1937,2026,2117,2210,2305,
>
> 2402,2501,2602,2705,2810,2917,3026,3137,3250,3365,3482,3601,3722,3845,3970,4
> 097}
>
> ID Number: A002522
> Sequence:
> 1,2,5,10,17,26,37,50,65,82,101,122,145,170,197,226,257,290,325,362,
>
> 401,442,485,530,577,626,677,730,785,842,901,962,1025,1090,1157,1226,
>            1297,1370,1445,1522,1601,1682
> Name:      n^2 + 1.Keywords:  nonn,easy
> Offset:    0
> Author(s): njas
>
> *** what? EASY in 4 dimensions but so weird as to be non-EIS in 3 and 2 dim?
> *** I don't believe it. Must be bug somehere. Hints??

No.  I have verified your calculations, and they are correct.

For dimension d = 3, a(n) counts the number of integers <= n^2+1 which are not
of the form 4^j (8k + 7).  Numbers of the latter form comprise a 2-regular set
(binary expressions accepted by a state machine), which implies that there is
a O(log(n)) (or thereabouts) algorithm for computing a(n).  lim n->inf a(n)/n^2 = 5/6.

If d >= 4, the four-square theorem guarantees that there will be an integer point
at every possible distance from the origin (where a possible distance is of the form
sqrt(k) for integer k >= 0).  For a d-dimensional sphere of radius n, there are
n^2+1 possible distances within the sphere (namely 0 <= sqrt(k) <= n).  This
means that A002522 will be your sequence for dimensions 4 and higher.

> w.meeussen.vdmcc at vandemoortele.be
> tel  +32 (0) 51 33 21 11
> fax +32 (0) 51 33 21 75