A057475 Number of k, 1 <= k <= n, such that gcd(n,k) = gcd(n+1,k) = 1.

1, 1, 1, 2, 1, 2, 3, 3, 2, 4, 3, 4, 5, 3, 4, 8, 5, 6, 7, 5, 5, 10, 7, 7, 9, 8, 8, 12, 7, 8, 15, 10, 9, 11, 8, 12, 17, 11, 9, 16, 11, 12, 19, 11, 11, 22, 15, 14, 17, 13, 15, 24, 17, 14, 17, 15, 17, 28, 15, 16, 29, 17, 18, 24, 15, 20, 31, 21, 15, 24, 23, 24, 35, 19, 19, 28, 18, 24, 31, 22

Offset: 1

Author

Leroy Quet, Sep 27 2000

Keywords

• nonn

Comments

Number of numbers between 1 and n-1 coprime to n(n+1).

It is conjectured that every positive integer appears. - Jon Perry, Dec 12 2002

Examples

			a(8) = 3 because 1, 5 and 7 are all relatively prime to both 8 and 9.
a(9) counts those numbers coprime to 90, i.e., 1 and 7, hence a(9) = 2.
		

Crossrefs

Cf. A000040, A000010, A065474, A118854, A124738, A124739, A124740, A124741.

Cf. A057828, A002378.

Programs

Magma

[#[k:k in [1..n]| Gcd(n,k) eq Gcd(n+1,k) and Gcd(n,k) eq 1]: n in [1..80]]; // Marius A. Burtea, Oct 15 2019

Maple

A057475 := proc(n)
    local a,k ;
    a :=  0;
    for k from 1 to n do
        if igcd(k,n) = 1 and igcd(k,n+1)=1 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A057475(n),n=1..80) ; # R. J. Mathar, May 13 2025

Mathematica

a[ n_ ] := Length @ Select[ Range[ n ], GCD[ n, # ] == GCD[ n + 1, # ] == 1 & ]; Table[ a[ n ], {n, 80} ] (* Ray Chandler, Dec 06 2006 *)

PARI

newphi(v)=local(vl,fl,np); vl=length(v); np=0; for (s=1,v[1],fl=false; for (r=1,vl,if (gcd(s,v[r])>1,fl=true; break)); if (fl==false,np++)); np
v=vector(2); for (i=1,500,v[1]=i; v[2]=i+1; print1(newphi(v)","))

Formula

From Reinhard Zumkeller, May 02 2006: (Start)

a(A000040(n)-1) = A000010(A000040(n)-1);

a(A000040(n)) = A000010(A000040(n)+1)-1;

a(A118854(n)-1) = a(A118854(n)). (End)

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 2/p^2) = 0.322634... (A065474). - Amiram Eldar, Dec 10 2024

a(n) = A057828(A002378(n)). - Ridouane Oudra, May 30 2025