|
|
A015613
|
|
a(n) = Sum_{i=1..n} phi(i) * (ceiling(n/i) - floor(n/i)).
|
|
1
|
|
|
0, 0, 1, 2, 5, 6, 11, 14, 19, 22, 31, 34, 45, 50, 57, 64, 79, 84, 101, 108, 119, 128, 149, 156, 175, 186, 203, 214, 241, 248, 277, 292, 311, 326, 349, 360, 395, 412, 435, 450, 489, 500, 541, 560, 583, 604, 649, 664, 705, 724, 755, 778, 829, 846, 885, 908, 943
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
a(n) is half the number of fractions reduced to lowest terms with numerator and denominator in {2, 3, ..., n}. a(5) = 5 = (1/2) * |{2/3, 2/5, 3/2, 3/4, 3/5, 4/3, 4/5, 5/2, 5/3, 5/4}|. - Stefano Spezia, Aug 11 2019
|
|
LINKS
|
|
|
FORMULA
|
a(n) = sum of phi(e) where e ranges over all nondivisors of n that are between 1 and n. - Joseph L. Pe, Oct 24 2002
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n=0, 0,
numtheory[phi](n)-1+a(n-1))
end:
|
|
MATHEMATICA
|
f[n_] := Module[{s, i}, s = 0; For[i = 1, i < n, i++, If[Mod[n, i] != 0, s = s + EulerPhi[i]]]; s]; Table[f[i], {i, 1, 100}]
|
|
PROG
|
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 0, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
j, k1 = j2, n//j2
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|