A098006 -id:A098006 - cp's OEIS frontend

A098047 Numbers not in A098006.

5, 20, 21, 22, 24, 28, 31, 33, 34, 36, 37, 38, 43, 45, 46, 48, 51, 52, 55, 58, 61, 67, 69, 70, 73, 79, 80, 82, 87, 88, 91, 97, 99, 100, 104, 106, 108, 112, 115, 117, 118, 123, 124, 127, 130, 132, 136, 138, 142, 145, 147, 148, 151, 152, 154, 156, 157, 159, 163, 166, 172

Offset: 1

Robert G. Wilson v, Sep 09 2004

nonn

In the Luca-Walsh paper it is shown that this sequence is infinite.
It can be shown that if a number k > 8, k not a power of 2, is in A098006, then k first appears for a prime p <= 1+k^2. For example, 26 first appears as A098006(123). The 123rd prime is 677, which equals 1+26^2. When this worst-case behavior occurs, then k/2 is a prime in A052291 and the corresponding 1+k^2 is in A052292. - T. D. Noe, Nov 13 2007
Banks and Luca (2004, 2005) called these numbers Robbins numbers. They proved that the lower asymptotic density of this sequence is > 1/3. - Amiram Eldar, Feb 13 2021

T. D. Noe, Table of n, a(n) for n=1..1000
William D. Banks and Florian Luca, Noncototients and Nonaliquots, arXiv:math/0409231 [math.NT], 2004.
William D. Banks and Florian Luca, Nonaliquots and Robbins numbers, Colloq. Math., Vol. 103, No. 1 (2005), pp. 27-32.
Florian Luca and P. G. Walsh, On the number of nonquadratic residues which are not primitive roots, Colloq. Math., Vol. 100, No. 1 (2004), pp. 91-93.
T. D. Noe, Finding primes for which (p-1)/2 - phi(p-1) = k.
Neville Robbins, Problem 002:18, Western Number Theory Problems, 16 & 19 Dec 2002. See p. 8; Florian Luca and Gary Wals, Solution, Western Number Theory Problems, 17 & 19 Dec 2004. See p. 2.

Cf. A098006.

t = Table[0, {200}]; Do[p = Prime[n]; a = (p - 1)/2 - EulerPhi[p - 1]; If[p < 201, t[[a]]++ ], {n, 2, 10^7}]; u = Table[ If[ t[[n]] != 0, n, 0], {n, 1, 200}]; Complement[ Range[200], u]

A051953 Cototient(n) := n - phi(n).

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27

Offset: 1

Labos Elemer, Dec 21 1999

Unlike totients, cototient(n+1) = cototient(n) never holds -- except 2-phi(2) = 3 - phi(3) = 1 -- because cototient(n) is congruent to n modulo 2. - Labos Elemer, Aug 08 2001
Theorem (L. Redei): b^a(n) == b^n (mod n) for every integer b. - Thomas Ordowski and Robert Israel, Mar 11 2016
Let S be the sum of the cototients of the divisors of n (A001065). S < n iff n is deficient, S = n iff n is perfect, and S > n iff n is abundant. - Ivan N. Ianakiev, Oct 06 2023

			n = 12, phi(12) = 4 = |{1, 5, 7, 11}|, a(12) = 12 - phi(12) = 8, numbers not exceeding 12 and not coprime to 12: {2, 3, 4, 6, 8, 9, 10, 12}.

T. D. Noe, Table of n, a(n) for n = 1..10000
J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), 55-58.
R. E. Jamison, The Helly bound for singular sums, Discrete Math., 249 (2002), 117-133.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26. For Richard Guy on his 99th birthday. May his sequence be unbounded.
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp. 83 (2014), 1903-1913.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Cototient

Cf. A000010, A001065 (inverse Möbius transform), A005278, A001274, A083254, A098006, A049586, A051612, A053579, A054525, A062790 (Möbius transform), A063985 (partial sums), A063986, A290087.
Records: A065385, A065386.
Number of zeros in the n-th row of triangle A054521. - Omar E. Pol, May 13 2016
Cf. A063740 (number of k such that cototient(k) = n). - M. F. Hasler, Jan 11 2018

a051953 n = n - a000010 n  -- Reinhard Zumkeller, Jan 21 2014

with(numtheory); A051953 := n->n-phi(n);

Table[n - EulerPhi[n], {n, 1, 80}] (* Carl Najafi, Aug 16 2011 *)

A051953(n) = n - eulerphi(n); \\ Michael B. Porter, Jan 28 2010

from sympy.ntheory import totient
print([i - totient(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 17 2017

a(n) = n - A000010(n).
Equals Mobius transform (A054525) of A001065. - Gary W. Adamson, Jul 11 2008
a(A006881(n)) = sopf(A006881(n)) - 1; a(A000040(n)) = 1. - Wesley Ivan Hurt, May 18 2013
G.f.: sum(n>=1, A000010(n)*x^(2*n)/(1-x^n) ). - Mircea Merca, Feb 23 2014
From Ilya Gutkovskiy, Apr 13 2017: (Start)
G.f.: -Sum_{k>=2} mu(k)*x^k/(1 - x^k)^2.
Dirichlet g.f.: zeta(s-1)*(1 - 1/zeta(s)). (End)
From Antti Karttunen, Sep 05 2018 & Apr 29 2022: (Start)
Dirichlet convolution square of A317846/A046644 gives this sequence + A063524.
a(n) = A003557(n) * A318305(n).
a(n) = A000010(n) - A083254(n).
a(n) = A318325(n) - A318326(n).
a(n) = Sum_{d|n} A062790(d) = Sum_{d|n, dA007431(d)*(A000005(n/d)-1).
a(n) = A048675(A318834(n)) = A276085(A353564(n)). [These follow from the formula below]
a(n) = Sum_{d|n, dA000010(d).
a(n) = A051612(n) - A001065(n).
(End)

A159611 Indices of the Fermat primes in the sequence of primes.

Original entry on oeis.org

2, 3, 7, 55, 6543

Offset: 1

Walter Nissen, Apr 16 2009

If it exists, a(6) >= primepi(2^(2^33)+1) which has more than 2*10^9 decimal digits. - Amiram Eldar, Sep 27 2024

			3, the 1st Fermat prime is the 2nd prime, so a(1) = 2.
17, the 3rd Fermat prime is the 7th prime, so a(3) = 7.

Index entries for sequences that are related to primes dividing Fermat numbers.

Cf. A000040 (primes), A000720, A019434 (Fermat primes).

Cf. A098006.

import Data.List (elemIndices)
a159611 n = a159611_list !! (n-1)
a159611_list = map (+ 2) $ elemIndices 0 a098006_list
-- Reinhard Zumkeller, Mar 26 2013

PrimePi/@{3,5,17,257,65537} (* Harvey P. Dale, Aug 07 2022 *)

for(i=0, 10, isprime(f=2^2^i+1) & print1(primepi(f), ", ")) \\ Michel Marcus, Apr 28 2016

a152155(n) = centerlift(Mod(3, 2^(2^n)+1)^(2^(2^n-1)))
print1(2, ", "); for(x=0, oo, if(a152155(x)==-1, print1(primepi(2^(2^x)+1), ", "))) \\ Felix Fröhlich, Apr 30 2021

A098006(a(n)) = 0. - Reinhard Zumkeller, Mar 26 2013

a(n) = A000720(A019434(n)). - Michel Marcus, Apr 29 2021

Name edited by Felix Fröhlich, Apr 30 2021

A134854 Least prime of the form 1 + p*2^n, where p is an odd prime.

Original entry on oeis.org

7, 13, 41, 113, 97, 193, 641, 769, 11777, 13313, 59393, 12289, 40961, 114689, 163841, 2424833, 6946817, 786433, 5767169, 7340033, 23068673, 155189249, 595591169, 1224736769, 167772161, 469762049, 2281701377, 3489660929, 12348030977

Offset: 1

T. D. Noe, Nov 13 2007

nonn

a(n) least prime such that A098006(pi(a(n))) = 2^(n-1). See A134855 for the values of p.

T. D. Noe, Table of n, a(n) for n=1..1000

Table[Select[1+2^n*Prime[Range[2,100]], PrimeQ, 1][[1]], {n,41}]

A134855 Least odd prime p such that 1 + p*2^n is also prime.

Original entry on oeis.org

3, 3, 5, 7, 3, 3, 5, 3, 23, 13, 29, 3, 5, 7, 5, 37, 53, 3, 11, 7, 11, 37, 71, 73, 5, 7, 17, 13, 23, 3, 239, 43, 113, 163, 59, 3, 89, 349, 5, 97, 3, 73, 11, 67, 101, 19, 101, 61, 23, 7, 17, 7, 233, 127, 5, 541, 29, 103, 71, 31, 53, 109, 179, 163, 71, 3, 929, 31, 23, 193, 101, 127

Offset: 1

T. D. Noe, Nov 13 2007

nonn

Let q = 1 + a(n)*2^n. Then q is least prime such that A098006(pi(q)) = 2^(n-1). See A134854 for the values of q.

a(n) = prime(k) for some k < 5*n for n <= 10000 . - Pierre CAMI, Jul 20 2014

Pierre CAMI, Table of n, a(n) for n = 1..10000 (First 1000 terms from T. D. Noe)

Cf. A098006, A134854.

Table[Select[Prime[Range[2,10000]], PrimeQ[1+2^k # ]&, 1][[1]], {k,100}]
lop[n_]:=Module[{k=3,c=2^n},While[!PrimeQ[1+k*c],k=NextPrime[k]];k]; Array[ lop,80] (* Harvey P. Dale, Sep 01 2022 *)

a(n) = p=3; t=2^n; while(!isprime(1+p*t), p=nextprime(p+1)); p \\ Colin Barker, Jul 22 2014

A134765 Least prime p for which (p-1)/2 - phi(p-1) = n, or 0 if there is no such prime.

Original entry on oeis.org

3, 7, 13, 19, 41, 0, 37, 31, 113, 43, 101, 71, 73, 67, 61, 79, 97, 131, 109, 103, 0, 0, 0, 191, 0, 139, 677, 127, 0, 419, 157, 0, 193, 0, 0, 151, 0, 0, 0, 199, 401, 683, 181, 0, 281, 0, 0, 431, 0, 283, 277, 0, 0, 659, 461, 0, 241, 211, 0, 743, 313, 0, 349, 271, 641, 827

Offset: 0

T. D. Noe, Nov 13 2007, Nov 19 2007

nonn

The graph of this sequence shows that for n>8 either a(n)=0 or a(n)<=1+n^2. See A098006 for the values of (p-1)/2 - phi(p-1) for odd primes p. Sequence A098047 lists the n for which a(n)=0. A134854(n)=a(2^(n-1)).

T. D. Noe, Table of n, a(n) for n = 0..10000
T. D. Noe, Finding primes p for which (p-1)/2 - phi(p-1) = k
T. D. Noe, Graph for n <= 50000

nn=1000; lc=Table[0,{nn}]; Do[p=Prime[n]; r=(p-1)/2-EulerPhi[p-1]; If[0

A280729 (p-1)/2 + phi(p-1) as p runs through the odd primes.

Original entry on oeis.org

2, 4, 5, 9, 10, 16, 15, 21, 26, 23, 30, 36, 33, 45, 50, 57, 46, 53, 59, 60, 63, 81, 84, 80, 90, 83, 105, 90, 104, 99, 113, 132, 113, 146, 115, 126, 135, 165, 170, 177, 138, 167, 160, 182, 159, 153, 183, 225, 186, 228, 215, 184, 225, 256, 261, 266, 207, 226, 236, 233

Offset: 1

Vincenzo Librandi, Jan 10 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A098006.

[(NthPrime(n)-1)/2+EulerPhi(NthPrime(n)-1): n in [2..100]];

A280729 := proc(n)
    local p;
    p := ithprime(n+1) ;
    (p-1)/2+numtheory[phi](p-1) ;
end proc: # R. J. Mathar, Jan 10 2017

Table[(n - 1)/2 + EulerPhi[n - 1], {n, Prime[Range[2, 100]]}]

a(n) = A098006(n)+2*A008330(n). - R. J. Mathar, Jan 10 2017

cp's OEIS Frontend

A098047 Numbers not in A098006.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A051953 Cototient(n) := n - phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A159611 Indices of the Fermat primes in the sequence of primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A134854 Least prime of the form 1 + p*2^n, where p is an odd prime.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

A134855 Least odd prime p such that 1 + p*2^n is also prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A134765 Least prime p for which (p-1)/2 - phi(p-1) = n, or 0 if there is no such prime.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

A280729 (p-1)/2 + phi(p-1) as p runs through the odd primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula