A160663 -id:A160663 - cp's OEIS frontend

A047800 Number of different values of i^2 + j^2 for i,j in [0, n].

1, 3, 6, 10, 15, 20, 27, 34, 42, 51, 61, 71, 83, 94, 106, 120, 135, 148, 165, 180, 198, 216, 235, 252, 273, 294, 315, 337, 360, 382, 408, 431, 457, 484, 508, 536, 567, 595, 624, 653, 687, 715, 749, 781, 813, 850, 884, 919, 957, 993, 1031, 1069, 1108, 1142

Offset: 0

Wouter Meeussen

a(n-1) is the number of distinct distances on an n X n pegboard. What is its asymptotic growth? Can it be efficiently computed for large n? - Charles R Greathouse IV, Jun 13 2013

Conjecture (after Landau and Erdős): a(n) ~ c * n^2 / sqrt(log(n)), where c = 0.79... . - Vaclav Kotesovec, Mar 10 2016

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..500 from T. D. Noe)
Paul Erdős, On sets of distances of n points, American Mathematical Monthly 53, pp. 248-250 (1946).
Vaclav Kotesovec, Graph - The asymptotic ratio
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 2, Leipzig B. G. Teubner, 1909, p. 643.
Hugo Pfoertner, Plot of asymptotic ratio, 1.44*10^6 terms, logarithmic scale for n, indicating c > 0.8.

Cf. A034966, A047801, A160663, A384797.

import Data.List (nub)
a047800 n = length $ nub [i^2 + j^2 | i <- [0..n], j <- [i..n]]
-- Reinhard Zumkeller, Oct 03 2012

Table[ Length@Union[ Flatten[ Table[ i^2+j^2, {i, 0, n}, {j, 0, n} ] ] ], {n, 0, 49} ]
nmax = 100; sq = Table[i^2 + j^2, {i, 0, nmax}, {j, 0, nmax}]; Table[Length@Union[Flatten[Table[Take[sq[[j]], n + 1], {j, 1, n + 1}]]], {n, 0, nmax}] (* Vaclav Kotesovec, Mar 09 2016 *)

a(n) = n++; #vecsort(vector(n^2, i, ((i-1)\n)^2+((i-1)%n)^2), , 8) \\ Charles R Greathouse IV, Jun 13 2013; edited by Michel Marcus, Jul 06 2025

a(n) = #setbinop((i,j)->i^2+j^2, [0..n]); \\ Michel Marcus, Jul 07 2025

def A047800(n): return len(set(i**2+j**2 for i in range(n+1) for j in range(i+1))) # Chai Wah Wu, Jul 07 2025

A226595 Lengths of maximal nontouching increasing paths in n X n grids.

Original entry on oeis.org

0, 2, 4, 7, 9, 12, 15, 17, 20, 24, 27, 29, 33, 36, 39

Offset: 1

Charles R Greathouse IV and Giovanni Resta, Jun 13 2013

The path is not allowed to touch itself, not even on single points. "Increasing" means that the (Euclidean) length of each line segment must be strictly longer than the last.

			An example for a(8)=17
-------------------------
01 02  .  .  .  . 05  .
..  . 03  . 04  .  . 18
09 07  .  . 06  .  . 16
..  .  .  .  .  .  . 14
..  .  .  .  .  .  . 12
..  . 08  .  .  .  .  .
10 17 15 13  .  .  .  .
..  .  .  . 11  .  .  .
-------------------------

Giovanni Resta, Illustration of a(2)-a(9)
Bert Dobbelaere, C++ program
Gordon Hamilton, $1,000,000 Unsolved Problem for Grade 8 (2011)
Stan Wagon, Illustration for a(2)-a(12)

Cf. A226596.

a(n) <= A226596(n) <= A160663(n-1).

a(10)-a(12) from Joseph DeVincentis via Charles R Greathouse IV, Oct 08 2015
a(13) from Charles R Greathouse IV, Oct 25 2015 using code from Joseph DeVincentis
a(14)-a(15) from Bert Dobbelaere, Oct 05 2018

A384797 a(n) = A047800(n) - A047800(n-1).

Original entry on oeis.org

2, 3, 4, 5, 5, 7, 7, 8, 9, 10, 10, 12, 11, 12, 14, 15, 13, 17, 15, 18, 18, 19, 17, 21, 21, 21, 22, 23, 22, 26, 23, 26, 27, 24, 28, 31, 28, 29, 29, 34, 28, 34, 32, 32, 37, 34, 35, 38, 36, 38, 38, 39, 34, 40, 42, 44, 43, 44, 42, 49, 42, 42, 46, 45, 51, 50, 46, 47, 50

Offset: 1

Hugo Pfoertner, Jun 17 2025

This is the number of distinct positive distances of the [0,n] X [0,n] points of a lattice square from the origin that are added when the size of the square is increased from n-1 to n. Among the newly added squared distances n^2, n^2+1^2, n^2+2^2, ..., n^2+n^2, some may already have occurred in smaller lattice point squares and are therefore not counted.

			a(1) = 2: Newly added squared distances are 1 and 2.
a(5) = 5: The squared distance 25=5^2+0^2 already occurs as 4^2+3^2.
a(13) = 11: There are 3 already represented squared distances, 13^2+0^2=12^2+5^2, 13^2+1^2=11^2+7^2, 13^2+4^2=11^2+8^2.

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Cf. A047800, A160663, A384798, A384799.

def A384797(n):
    s = set(i**2+j**2 for i in range(n) for j in range(i+1))
    return n+1-sum(1 for i in range(n+1) if n**2+i**2 in s) # Chai Wah Wu, Jul 07 2025

A226596 Lengths of maximal non-crossing and non-overlapping increasing paths in n X n grids.

Original entry on oeis.org

0, 2, 4, 7, 10, 13, 16, 20, 22

Offset: 1

Charles R Greathouse IV and Giovanni Resta, Jun 13 2013

The path is allowed to touch but not cross itself on single points, but not on segments of any length. "Increasing" means that the (Euclidean) length of each line segment must be strictly longer than the last.

			A solution for the case a(8)=20 is
-------------------------
01 02  .  .  .  .  . 16
..  . 03  .  .  .  . 14
09  . 15  . 05  .  . 12
..  . 04  .  .  .  .  .
..  . 06 13  . 07  . 21
..  . 08  . 11  .  . 19
10  .  .  .  .  .  . 17
20 18  .  .  .  .  .  .
-------------------------

Giovanni Resta, Illustration of a(2)-a(9)
Gordon Hamilton, $1,000,000 Unsolved Problem for Grade 8 (2011)

Cf. A226595.

a(n) <= A160663(n-1).

cp's OEIS Frontend

A047800 Number of different values of i^2 + j^2 for i,j in [0, n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A226595 Lengths of maximal nontouching increasing paths in n X n grids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A384797 a(n) = A047800(n) - A047800(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A226596 Lengths of maximal non-crossing and non-overlapping increasing paths in n X n grids.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula