Vous aurez la démonstration visuelle ici =>
NOM :
Number of pairs (p/q, k) with gcd(p,q)=1, 1 <= p < q <= n and 1 <= k <= n-1.
DONNÉES :
0, 1, 6, 15, 36, 55, 102, 147, 216, 279, 410, 495, 684, 819, 994, 1185, 1520, 1717, 2142, 2413, 2780, 3129, 3762, 4117, 4776, 5275, 5954, 6507, 7532, 8033, 9210, 10013, 10976, 11847, 13022, 13825, 15516, 16613, 17974, 19071, 21160, 22181, 24486, 25929, 27588, 29205, 31970, 33417, 36144, 37877
OFFSET (décalage) :
1
COMMENTAIRES :
For a given n, each term a(n) counts pairs (p/q, k) where p/q is a reduced fraction with 1 <= p < q <= n and k is an integer in {1, ..., n-1}.
The number of such reduced fractions p/q equals Sum_{m=2..n} phi(m) = A002088(n) - 1.
This is also the number of interior fractions (excluding 0/1 and 1/1) of the Farey sequence of order n.
Since k can be chosen independently in {1,..., n-1}, the total count is a(n) = (n - 1) * (A002088(n) - 1).
This sequence was first observed in connection with a folding model on an n-unit strip using two perpendicular 180-degree crease directions. The definition given here, however, uses only the arithmetic structure of reduced fractions and the parameter k.
RÉFÉRENCES :
~
LIENS :
Jean-Louis Lascoux, Table of n, a(n) for n = 1..1001 ;
Alexander Bogomolny, Farey Series ;
Jean-Louis Lascoux, Flat-Möbius World ;
Eric Weisstein's World of Mathematics, Farey Sequence
FORMULE :
a(n) = (n - 1) * Sum_{k=2..n} phi(k).
a(n) = (n - 1) * (A002088(n) - 1).
Asymptotic: a(n) ~ (3 / Pi^2) * n^3.
EXEMPLE :
n = 6: Sum_{k=2..6} phi(k) = 11; multiply by (6-1) = 5 gives a(6) = 55.
Programme Maple :
with(numtheory):
a := n -> (n-1)*add(phi(k), k=2..n):
seq(a(n), n=1..40);
Programme Mathematica :
a[n_] := (n - 1) * Sum[EulerPhi[k], {k, 2, n}];
Array[a, 40, 1]
PROGRAMME (autre langage) :
(Python)
import sympy as sp
def a(n): return (n-1)*sum(sp.totient(k) for k in range(2, n+1))
print([a(n) for n in range(1, 41)])
(PARI)
a(n)=my(s=0); for(k=2, n, s+=eulerphi(k)); (n-1)*s;
vector(40, j, a(j))
RÉFÉRENCES CROISÉES :
Cf. A000010, A002088.
MOTS-CLÉS :
nonn,easy
AUTEUR :
Jean-Louis Lascoux — 2025-12-06
