login
A073453
Number of distinct remainders arising when n is divided by all primes up to n.
7
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
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
KEYWORD
nonn
AUTHOR
Labos Elemer, Aug 02 2002
STATUS
approved