A073453 Number of distinct remainders arising when n is divided by all primes up to n.

0, 1, 2, 2, 3, 2, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 6, 6, 7, 7, 6, 6, 7, 8, 8, 8, 8, 8, 9, 8, 9, 10, 10, 9, 8, 9, 10, 10, 9, 10, 11, 11, 12, 12, 12, 12, 13, 14, 14, 14, 13, 13, 14, 15, 14, 14, 13, 13, 14, 15, 16, 16, 16, 17, 16, 15, 16, 16, 16, 16, 17, 18, 19, 19, 19, 19, 18, 18, 19, 19, 20

Offset: 1

Author

Labos Elemer, Aug 02 2002

Keywords

• nonn

Examples

			n=25: Primes are (2,3,5,7,11,13,17,19,23), remainders are (1,1,0,4,3,12,8,6,2), distinct remainders are {0,1,2,3,4,6,8,12} which has 8 members, so a(25) = 8.
		

Links

• Michel Marcus, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A072530, A072531, A073454, A000720.

Programs

Mathematica

Table[Length[Union[Table[Mod[w, Prime[j]], {j, 1, PrimePi[w]}]]], {w, 1, 256}]
Table[Length[Union[Mod[n,Prime[Range[PrimePi[n]]]]]],{n,100}] (* Harvey P. Dale, Jul 04 2021 *)

PARI

a(n) = #Set(vector(primepi(n), k, n % prime(k))); \\ Michel Marcus, May 28 2016

PARI

a(n) = #Set(apply(p->n%p, primes([2,n]))) \\ Charles R Greathouse IV, Jun 17 2016

Formula

See program below.

a(n) = n + 1 - Sum_{k=1..n-1} ( floor((k-1)!^(n-1)/(n-k+1))-floor(((k-1)!^(n-1)-1)/(n-k+1)) ). - Anthony Browne, May 27 2016