A057828 -id:A057828 - cp's OEIS frontend

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

Leroy Quet, Sep 27 2000

nonn

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

			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.

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

Cf. A057828, A002378.

[#[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

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

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

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)","))

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

A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.

Original entry on oeis.org

3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42, 48, 54, 60, 62, 68, 72, 80, 84, 90, 98, 108, 110, 132, 138, 140, 150, 180, 182, 198, 252, 318, 360, 398, 468, 570, 572, 930, 1722

Offset: 1

Hans Ruegg, Jul 21 2012

No further terms < 10^10.
This sequence is based on a remark in a paper distributed over the Internet (see the Leo Moser link) under the heading "Unsolved Problems and Conjectures" (page 84):
"Is 968 the largest number n such that for all k with (n, k) = 1 and n > k^2, n - k^2 is prime? (Erdős)"
The statement by Moser contains an error: 968 does NOT have this property (968-25*25 = 343 = 7*7*7), and the largest such number (1722) is larger than 968.
A224076(n) <= A064272(a(n)+1). - Reinhard Zumkeller, Mar 31 2013

			For example, the number 20 is part of this sequence because 20-1*1 = 19 (prime), and 20-3*3 = 11 (prime). Not considered are 20-2*2 and 20-4*4, because 2 and 4 are not relative primes to 20.

Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group 2004, page 84.

Cf. A065428.
Cf. A057828, A000290, A010051.
Cf. A224075; subsequence of A008864.

a214583 n = a214583_list !! (n-1)
a214583_list = filter (p 3 1) [2..] where
   p i k2 x = x <= k2 || (gcd k2 x > 1 || a010051' (x - k2) == 1) &&
                         p (i + 2) (k2 + i) x
-- Reinhard Zumkeller, Mar 31 2013, Jul 22 2012

Reap[For[p = 2, p < 2000, p = NextPrime[p], n = p+1; q = True; k = 1; While[k*k < n, If[GCD[k, n] == 1, If[! PrimeQ[n - k^2], q = False; Break[]]]; k += 1]; If[q, Sow[n]]]] [[2, 1]] (* Jean-François Alcover, Oct 11 2013, after Joerg Arndt's Pari program *)
gQ[n_]:=AllTrue[n-#^2&/@Select[Range[Floor[Sqrt[n]]],CoprimeQ[ #, n]&], PrimeQ]; Select[Range[2000],gQ] (* The program uses the AllTrue function from Mathematica version 10 *) (* Harvey P. Dale, Dec 02 2018 *)

N=10^10;
default(primelimit,N);
{ forprime (p=2, N,
    n = p + 1;
    q = 1;
    k = 1;
    while ( k*k < n,
        if ( gcd(k,n)==1,
            if ( ! isprime(n-k^2),  q=0; break() );
        );
        k += 1;
    );
    if ( q, print1(n,", ") );
); }
/* Joerg Arndt, Jul 21 2012 */

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 21, 24, 28, 40, 48, 56, 60, 72, 88, 120, 168, 240, 840

Offset: 1

Jianing Song, Apr 29 2018

Numbers k such that A046073(k) = A057828(k).
There are exactly 25 members in this sequence and this is the full list. Note that for other k, A046073(k) > A057828(k).
From Jianing Song, Feb 14 2019: (Start)
For the proof that this sequence is finite, we will show that there are no terms > 130729.
Let A(n) = A046073(n) be the number of coprime quadratic residues modulo n. By definition, if k is a term then A(k) <= sqrt(k), that is, A(k)/sqrt(k) <= 1. Let f(n) = A(n)/sqrt(n), then f(n) is multiplicative with f(2) = sqrt(2)/2, f(4) = 1/2, f(2^e) = 2^(e/2 - 3) for e >= 3, f(p^e) = ((p - 1)/2)*p^(e/2 - 1) when p > 2. Note that f(2^e) >= a(2^3), f(p^e) >= f(p), f(p) > 1 when p >= 7. For every number n, we have:
a) if n is divisible by a prime >= 127, then f(n) >= f(2^3)*f(3)*f(5)*f(127) = sqrt(1323/1270) > 1.
b) if n is divisible by two distinct primes >= 23, then f(n) >= f(2^3)*f(3)*f(5)*f(23)*f(29) = sqrt(11858/10005) > 1.
So if k > 130729 is a term, then all prime factors of k are no greater than 113, and k contains at most one prime factor >= 23. On the other hand, if all prime factors of k are no greater than 19, then 53881 is a coprime quadratic residue modulo k because 53881 is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17 and 19, but 53881 is not a perfect square, a contradiction. As a result, k must contain exactly one prime factor p in [23, 113].
Now if a number m is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17, 19 and p, then m is a coprime quadratic residue modulo k. Consider the numbers 53881, 86641, 87481, 102001, 117049 and 130729. At least one of them is a coprime quadratic residue modulo each prime p in [23, 113], so at least one of them is a coprime quadratic residue modulo k, but none of them is a square, a contradiction! (End)

			All coprime quadratic residues modulo 21 are 1, 4, 16 and they are all squares, so 21 is a term.
All coprime quadratic residues modulo 840 are 1, 121, 169, 289, 361, 529 and they are all squares, so 840 is a term.
249 == 23^2 is a coprime quadratic residue modulo 280 but 249 is not a square number, so 280 is not a term.

Cf. A046073, A057828, A214583.

A254328 is a subsequence.

for(k=1, 130729, if(eulerphi(k)/2^#znstar(k)[2]<=sqrt(k), for(j=1, k, if(gcd(j,k)==1&&!issquare(j^2%k), break()); if(j==k, print1(k, ", "))))) \\ Jianing Song, Feb 15 2019

A074818 Number of integers in {1, 2, ..., prime(n)} that are coprime to n.

Original entry on oeis.org

2, 2, 4, 4, 9, 5, 15, 10, 16, 12, 29, 13, 38, 19, 26, 27, 56, 21, 64, 29, 42, 36, 80, 30, 78, 47, 69, 46, 106, 31, 123, 66, 84, 66, 103, 51, 153, 78, 104, 70, 175, 52, 187, 88, 106, 96, 207, 75, 195, 92, 147, 111, 237, 84, 187, 113, 170, 131, 273, 75, 279, 142, 176

Offset: 1

Joseph L. Pe, Oct 04 2002

nonn

Compare the definition of a(n) to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n.

			There are five numbers in {1, 2, ..., prime(6) = 13} that are coprime to 6, i.e. 1, 5, 7, 11, 13. Hence a(6) = 5.

Cf. A000010, A000040, A004648, A008683.

Cf. A129139, A074919, A074882, A074933, A074934, A057828.

with(numtheory): seq(add(mobius(d)*floor(ithprime(n)/d), d in divisors(n)), n=1..100) ; # Ridouane Oudra, Jun 04 2025

h[n_] := Module[{l}, l = {}; For[i = 1, i <= Prime[n], i++, If[GCD[i, n] == 1, l = Append[l, i]]]; l]; Table[Length[h[i]], {i, 1, 100}]

a(n) = sum(k=1, prime(n), gcd(k, n)==1); \\ Michel Marcus, Jun 04 2025

a(n) = my(p = prime(n)); eulerphi(n) * (p \ n) + sum(i = (p \ n)*n + 1, p, gcd(i, n) == 1); \\ David A. Corneth, Jun 04 2025

a(n) = Sum_{d|n} mu(d)*floor(prime(n)/d). - Ridouane Oudra, Jun 04 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A074818 Number of integers in {1, 2, ..., prime(n)} that are coprime to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula