cp's OEIS Frontend

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

%I A057475 #34 May 31 2025 00:00:16
%S A057475 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,
%T A057475 9,11,8,12,17,11,9,16,11,12,19,11,11,22,15,14,17,13,15,24,17,14,17,15,
%U A057475 17,28,15,16,29,17,18,24,15,20,31,21,15,24,23,24,35,19,19,28,18,24,31,22
%N A057475 Number of k, 1 <= k <= n, such that gcd(n,k) = gcd(n+1,k) = 1.
%C A057475 Number of numbers between 1 and n-1 coprime to n(n+1).
%C A057475 It is conjectured that every positive integer appears. - _Jon Perry_, Dec 12 2002
%F A057475 From _Reinhard Zumkeller_, May 02 2006: (Start)
%F A057475 a(A000040(n)-1) = A000010(A000040(n)-1);
%F A057475 a(A000040(n)) = A000010(A000040(n)+1)-1;
%F A057475 a(A118854(n)-1) = a(A118854(n)). (End)
%F A057475 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
%F A057475 a(n) = A057828(A002378(n)). - _Ridouane Oudra_, May 30 2025
%e A057475 a(8) = 3 because 1, 5 and 7 are all relatively prime to both 8 and 9.
%e A057475 a(9) counts those numbers coprime to 90, i.e., 1 and 7, hence a(9) = 2.
%p A057475 A057475 := proc(n)
%p A057475     local a,k ;
%p A057475     a :=  0;
%p A057475     for k from 1 to n do
%p A057475         if igcd(k,n) = 1 and igcd(k,n+1)=1 then
%p A057475             a := a+1 ;
%p A057475         end if;
%p A057475     end do:
%p A057475     a ;
%p A057475 end proc:
%p A057475 seq(A057475(n),n=1..80) ; # _R. J. Mathar_, May 13 2025
%t A057475 a[ n_ ] := Length @ Select[ Range[ n ], GCD[ n, # ] == GCD[ n + 1, # ] == 1 & ]; Table[ a[ n ], {n, 80} ] (* _Ray Chandler_, Dec 06 2006 *)
%o A057475 (PARI)
%o A057475 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
%o A057475 v=vector(2); for (i=1,500,v[1]=i; v[2]=i+1; print1(newphi(v)","))
%o A057475 (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
%Y A057475 Cf. A000040, A000010, A065474, A118854, A124738, A124739, A124740, A124741.
%Y A057475 Cf. A057828, A002378.
%K A057475 nonn
%O A057475 1,4
%A A057475 _Leroy Quet_, Sep 27 2000