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,3

Links

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

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

Example

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.

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 *)

Prog

(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

Crossrefs

Cf. A072530, A072531, A073454, A000720.

Sequence in context: A069352 A322832 A348389 * A123229 A127095 A249871

Adjacent sequences: A073450 A073451 A073452 * A073454 A073455 A073456

Keyword

nonn

Author

Labos Elemer, Aug 02 2002

Status

approved