A014665 Number of new fractions m/n < 1, where (m,n)=1 and "new" means the value of m*n has not occurred before.

1, 1, 2, 2, 4, 1, 6, 4, 6, 2, 10, 3, 12, 3, 5, 8, 16, 3, 18, 6, 7, 5, 22, 5, 20, 6, 18, 8, 28, 4, 30, 16, 12, 8, 18, 9, 36, 9, 14, 12, 40, 6, 42, 13, 17, 11, 46, 11, 42, 10, 19, 15, 52, 9, 25, 20, 21, 14, 58, 10, 60, 15, 28, 32, 29, 9, 66, 21, 26, 11, 70, 20, 72, 18, 23, 23, 42, 11, 78, 23, 54

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Examples

			{1}, {1/2}, {1/3,2/3}, {1/4,3/4}, {1/5,...,4/5}, {5/6}, ...
		

References

• S. W. Golomb, personal communication, Svalbard, Norway, 7/97.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe).

Crossrefs

Cf. A027435, A236309.

Programs

Mathematica

a[1] = 1;
a[n_] := Sum[Boole[GCD[i, n] == 1 && Sum[t = i*n/d; Boole[GCD[t, d] == 1 && t < d < n], {d, Divisors[i*n]}] == 0], {i, 1, n - 1}];
Array[a, 100] (* Jean-François Alcover, Sep 05 2019, from PARI *)

PARI

a(n)=if(n==1, 1, sum(i=1, n-1, gcd(i,n) == 1 && 0==sumdiv(i*n, d, my(t=i*n/d); gcd(t,d)==1 && dAndrew Howroyd, Nov 16 2018

Extensions

Example corrected by and more terms from Olivier Gérard, Feb 1999