A049084 -id:A049084 - cp's OEIS frontend

A064989 Multiplicative with a(2^e) = 1 and a(p^e) = prevprime(p)^e for odd primes p.

1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 11, 5, 6, 1, 13, 4, 17, 3, 10, 7, 19, 2, 9, 11, 8, 5, 23, 6, 29, 1, 14, 13, 15, 4, 31, 17, 22, 3, 37, 10, 41, 7, 12, 19, 43, 2, 25, 9, 26, 11, 47, 8, 21, 5, 34, 23, 53, 6, 59, 29, 20, 1, 33, 14, 61, 13, 38, 15, 67, 4, 71, 31, 18, 17, 35, 22, 73, 3, 16

Offset: 1

Vladeta Jovovic, Oct 30 2001

From Antti Karttunen, May 12 2014: (Start)
a(A003961(n)) = n for all n. [This is a left inverse function for the injection A003961.]
Bisections are A064216 (the terms at odd indices) and A064989 itself (the terms at even indices), i.e., a(2n) = a(n) for all n.
(End)
From Antti Karttunen, Dec 18-21 2014: (Start)
When n represents an unordered integer partition via the indices of primes present in its prime factorization (for n >= 2, n corresponds to the partition given as the n-th row of A112798) this operation subtracts one from each part. If n is of the form 2^k (a partition having just k 1's as its parts) the result is an empty partition (which is encoded by 1, having an "empty" factorization).
For all odd numbers n >= 3, a(n) tells which number is located immediately above n in square array A246278. Cf. also A246277.
(End)
Alternatively, if numbers are represented as the multiset of indices of prime factors with multiplicity, this operation subtracts 1 from each element and discards the 0's. - M. F. Hasler, Dec 29 2014

			a(20) = a(2^2*5) = a(2^2)*a(5) = prevprime(5) = 3.

Harry J. Smith (first 1000 terms) & Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A064216 (odd bisection), A003961 (inverse), A151799.
Cf. A000040, A008578, A027746, A032742, A049084, A052126, A055396, A061395, A112798, A249817, A249818.
Other sequences whose definition involve or are some other way related with this sequence: A105560, A108951, A118306, A122111, A156552, A163511, A200746, A241909, A243070, A243071, A243072, A243073, A244319, A245605, A245607, A246165, A246266, A246268, A246277, A246278, A246361, A246362, A246371, A246372, A246373, A246374, A246376, A246380, A246675, A246682, A249745, A250470.
Similar prime-shifts towards smaller numbers: A252461, A252462, A252463.

a064989 1 = 1
a064989 n = product $ map (a008578 . a049084) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A064989 n) (if (= 1 n) n (apply * (map (lambda (k) (if (zero? k) 1 (A000040 k))) (map -1+ (map A049084 (factor n)))))))
;; Antti Karttunen, May 12 2014
(definec (A064989 n) (if (= 1 n) n (* (A008578 (A055396 n)) (A064989 (A032742 n))))) ;; One based on given recurrence and utilizing memoizing definec-macro.
(definec (A064989 n) (cond ((= 1 n) n) ((even? n) (A064989 (/ n 2))) (else (A163511 (/ (- (A243071 n) 1) 2))))) ;; Corresponds to one of the alternative formulas, but is very unpractical way to compute this sequence. - Antti Karttunen, Dec 18 2014

q:= proc(p) prevprime(p) end proc: q(2):= 1:
[seq(mul(q(f[1])^f[2], f = ifactors(n)[2]), n = 1 .. 1000)]; # Robert Israel, Dec 21 2014

Table[Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n, {n, 81}] (* Michael De Vlieger, Jan 04 2016 *)

{ for (n=1, 1000, f=factor(n)~; a=1; j=1; if (n>1 && f[1, 1]==2, j=2); for (i=j, length(f), a*=precprime(f[1, i] - 1)^f[2, i]); write("b064989.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 02 2009

a(n) = {my(f = factor(n)); for (i=1, #f~, if ((p=f[i,1]) % 2, f[i,1] = precprime(p-1), f[i,1] = 1);); factorback(f);} \\ Michel Marcus, Dec 18 2014

A064989(n)=factorback(Mat(apply(t->[max(precprime(t[1]-1),1),t[2]],Vec(factor(n)~))~)) \\ M. F. Hasler, Dec 29 2014

from sympy import factorint, prevprime
from operator import mul
from functools import reduce
def a(n):
    f=factorint(n)
    return 1 if n==1 else reduce(mul, [1 if i==2 else prevprime(i)**f[i] for i in f])
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 15 2017

from math import prod
from sympy import prevprime, factorint
def A064989(n): return prod(prevprime(p)**e for p, e in  factorint(n>>(~n&n-1).bit_length()).items()) # Chai Wah Wu, Jan 05 2023

From Antti Karttunen, Dec 18 2014: (Start)
If n = product A000040(k)^e(k) then a(n) = product A008578(k)^e(k) [where A000040(n) gives the n-th prime, and A008578(n) gives 1 for 1 and otherwise the (n-1)-th prime].
a(1) = 1; for n > 1, a(n) = A008578(A055396(n)) * a(A032742(n)). [Above formula represented as a recurrence. Cf. A252461.]
a(1) = 1; for n > 1, a(n) = A008578(A061395(n)) * a(A052126(n)). [Compare to the formula of A252462.]
This prime-shift operation is used in the definitions of many other sequences, thus it can be expressed in many alternative ways:
a(n) = A200746(n) / n.
a(n) = A242424(n) / A105560(n).
a(n) = A122111(A122111(n)/A105560(n)) = A122111(A052126(A122111(n))). [In A112798-partition context: conjugate, remove the largest part (the largest prime factor), and conjugate again.]
a(1) = 1; for n > 1, a(2n) = a(n), a(2n+1) = A163511((A243071(2n+1)-1) / 2).
a(n) = A249818(A250470(A249817(n))). [A250470 is an analogous operation for "going one step up" in the square array A083221 (A083140).]
(End)
Product_{k=1..n} a(k) = n! / A307035(n). - Vaclav Kotesovec, Mar 21 2019
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-q(p))) = 0.220703928... , where q(p) = prevprime(p) (A151799) if p > 2 and q(2) = 1. - Amiram Eldar, Nov 18 2022

A003963 Fully multiplicative with a(p) = k if p is the k-th prime.

Original entry on oeis.org

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

Offset: 1

Marc LeBrun

a(n) is the Matula number of the rooted tree obtained from the rooted tree T having Matula number n, by contracting its edges that emanate from the root. Example: a(49) = 16. Indeed, the rooted tree with Matula number 49 is the tree obtained by merging two copies of the tree Y at their roots. Contracting the two edges that emanate from the root, we obtain the star tree with 4 edges having Matula number 16. - Emeric Deutsch, May 01 2015
The Matula (or Matula-Goebel) number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. - Emeric Deutsch, May 01 2015
a(n) is the product of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(75) = 18; indeed, the partition having Heinz number 75 = 3*5*5 is [2,3,3] and 2*3*3 = 18. - Emeric Deutsch, Jun 03 2015
Let T be the free-commutative-monoid monad on the category Set. Then for each set N we have a canonical function m from TTN to TN. If we let N = {1, 2, 3, ...} and enumerate the primes in the usual way (A000040) then unique prime factorization gives a canonical bijection f from N to TN. Then the sequence is given by a(n) = f^-1(m(T(f)(f(n)))). - Oscar Cunningham, Jul 18 2019

T. D. Noe, Table of n, a(n) for n = 1..10000
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
F. Göbel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Göbel numbers
Index entries for sequences computed from indices in prime factorization

Cf. A000720, A001221, A001222, A027748, A049084, A056239, A064553, A124010, A156552, A215366, A227184, A241909, A243354, A243499, A243504.

Product of entries on row n of A112798.

a003963 n = product $
   zipWith (^) (map a049084 $ a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Jun 30 2012

with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then pi(n) else a(r(n))*a(s(n)) end if end proc: seq(a(n), n = 1 .. 88);
# Alternative:
seq(mul(numtheory:-pi(t[1])^t[2], t=ifactors(n)[2]), n=1..100); # Robert Israel, May 01 2015

a[n_] := Times @@ (PrimePi[ #[[1]] ]^#[[2]]& /@ FactorInteger[n]); a[1] = 1; Table[a[n], {n, 1, 88}]

a(n)=f=factor(n);prod(i=1,#f[,1],primepi(f[i,1])^f[i,2]) \\ Charles R Greathouse IV, Apr 26 2012; corrected by Rémy Sigrist, Jul 18 2019

a(n) = {f = factor(n); for (i=1, #f~, f[i, 1] = primepi(f[i, 1]); ); factorback(f); } \\ Michel Marcus, Feb 08 2015

A003963(n)={n=factor(n); n[,1]=apply(primepi,n[,1]); factorback(n)} \\ M. F. Hasler, May 03 2018

from math import prod
from sympy import primepi, factorint
def A003963(n): return prod(primepi(p)**e for p, e in factorint(n).items()) # Chai Wah Wu, Nov 17 2022

If n = product prime(k)^e(k) then a(n) = product k^e(k).
Multiplicative with a(p^e) = A000720(p)^e. - David W. Wilson, Aug 01 2001
a(n) = Product_{k=1..A001221(n)} A049084(A027748(n,k))^A124010(n,k). - Reinhard Zumkeller, Jun 30 2012
Rec. eq.: a(1)=1, a(k-th prime) = a(k), a(rs)=a(r)a(s). The Maple program is based on this. - Emeric Deutsch, May 01 2015
a(n) = A243504(A241909(n)) = A243499(A156552(n)) = A227184(A243354(n)) - Antti Karttunen, Mar 07 2017

A055396 Smallest prime dividing n is a(n)-th prime (a(1)=0).

Original entry on oeis.org

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

Offset: 1

Henry Bottomley, May 15 2000

nonn

Grundy numbers of the game in which you decrease n by a number prime to n, and the game ends when 1 is reached. - Eric M. Schmidt, Jul 21 2013
a(n) = the smallest part of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1...r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(21) = 2; indeed, the partition having Heinz number 21 = 3*7 is [2,4]. - Emeric Deutsch, Jun 04 2015
a(n) is the number of numbers whose largest proper divisor is n, i.e., for n>1, number of occurrences of n in A032742. - Stanislav Sykora, Nov 04 2016
For n > 1, a(n) gives the number of row where n occurs in arrays A083221 and A246278. - Antti Karttunen, Mar 07 2017

			a(15) = 2 because 15=3*5, 3<5 and 3 is the 2nd prime.

John H. Conway, On Numbers and Games, 2nd Edition, p. 129.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021.
Wikipedia, Nimber (explains the term Grundy number).
Index entries for sequences computed from indices in prime factorization
Index entries for sequences generated by sieves

Cf. A004280, A020639, A032742, A038179, A049084, A055399, A061395, A215366, A243055, A257993, A276086.

Cf. also A078898, A246277, A250469 and arrays A083221 and A246278.

a055396 = a049084 . a020639  -- Reinhard Zumkeller, Apr 05 2012

with(numtheory):
a:= n-> `if`(n=1, 0, pi(min(factorset(n)[]))):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 03 2013

a[1] = 0; a[n_] := PrimePi[ FactorInteger[n][[1, 1]] ]; Table[a[n], {n, 1, 96}](* Jean-François Alcover, Jun 11 2012 *)

a(n)=if(n==1,0,primepi(factor(n)[1,1])) \\ Charles R Greathouse IV, Apr 23 2015

from sympy import primepi, isprime, primefactors
def a049084(n): return primepi(n)*(1*isprime(n))
def a(n): return 0 if n==1 else a049084(min(primefactors(n))) # Indranil Ghosh, May 05 2017

From Reinhard Zumkeller, May 22 2003: (Start)
a(n) = A049084(A020639(n)).
A000040(a(n)) = A020639(n); a(n) <= A061395(n).
(End)
From Antti Karttunen, Mar 07 2017: (Start)
A243055(n) = A061395(n) - a(n).
a(A276086(n)) = A257993(n).
(End)

A019434 Fermat primes: primes of the form 2^(2^k) + 1, for some k >= 0.

Original entry on oeis.org

3, 5, 17, 257, 65537

Offset: 1

N. J. A. Sloane, David W. Wilson

It is conjectured that there are only 5 terms. Currently it has been shown that 2^(2^k) + 1 is composite for 5 <= k <= 32 (see Eric Weisstein's Fermat Primes link). - Dmitry Kamenetsky, Sep 28 2008
No Fermat prime is a Brazilian number. So Fermat primes belong to A220627. For proof see Proposition 3 page 36 in "Les nombres brésiliens" in Links. - Bernard Schott, Dec 29 2012
This sequence and A001220 are disjoint (see "Other theorems about Fermat numbers" in Wikipedia link). - Felix Fröhlich, Sep 07 2014
Numbers n > 1 such that n * 2^(n-2) divides (n-1)! + 2^(n-1). - Thomas Ordowski, Jan 15 2015
From Jaroslav Krizek, Mar 17 2016: (Start)
Primes p such that phi(p) = 2*phi(p-1); primes from A171271.
Primes p such that sigma(p-1) = 2p - 3.
Primes p such that sigma(p-1) = 2*sigma(p) - 5.
For n > 1, a(n) = primes p such that p = 4 * phi((p-1) / 2) + 1.
Subsequence of A256444 and A256439.
Conjectures:
1) primes p such that phi(p) = 2*phi(p-2).
2) primes p such that phi(p) = 2*phi(p-1) = 2*phi(p-2).
3) primes p such that p = sigma(phi(p-2)) + 2.
4) primes p such that phi(p-1) + 1 divides p + 1.
5) numbers n such that sigma(n-1) = 2*sigma(n) - 5. (End)
Odd primes p such that ratio of the form (the number of nonnegative m < p such that m^q == m (mod p))/(the number of nonnegative m < p such that -m^q == m (mod p)) is a divisor of p for all nonnegative q. - Juri-Stepan Gerasimov, Oct 13 2020
Numbers n such that tau(n)*(number of distinct ratio (the number of nonnegative m < n such that m^q == m (mod n))/(the number of nonnegative m < n such that -m^q == m (mod n))) for nonnegative q is equal to 4. - Juri-Stepan Gerasimov, Oct 22 2020
The numbers of primitive roots for the five known terms are 1, 2, 8, 128, 32768. - Gary W. Adamson, Jan 13 2022
Prime numbers such that every residue is either a primitive root or a quadratic residue. - Keith Backman, Jul 11 2022
If there are only 5 Fermat primes, then there are only 31 odd order groups which have a 2-group automorphism group. See the Miles Englezou link for a proof. - Miles Englezou, Mar 10 2025

John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 137-141, 197.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
C. F. Gauss, Disquisitiones Arithmeticae, Yale, 1965; see Table 1, p. 458.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, pp. 78-79.
Richard K. Guy, Unsolved Problems in Number Theory, A3.
Hardy and Wright, An Introduction to the Theory of Numbers, bottom of page 18 in the sixth edition, gives an heuristic argument that this sequence is finite.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 7, 70.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 136-137.

Anas AbuDaqa, Amjad Abu-Hassan, and Muhammad Imam, Taxonomy and Practical Evaluation of Primality Testing Algorithms, arXiv:2006.08444 [cs.CR], 2020.
Cyril Banderier, Pepin's Criterion For Fermat Numbers (in French)
Kent D. Boklan and John H. Conway, Expect at most one billionth of a new Fermat Prime!, arXiv:1605.01371 [math.NT], 2016.
P. Bruillard, S.-H. Ng, E. Rowell, and Z. Wang, On modular categories, arXiv:1310.7050 [math.QA], 2013-2015.
C. K. Caldwell, The Prime Glossary, Fermat number
Miles Englezou, Proof that 5 Fermat primes implies 31 odd order groups with 2-group automorphism groups
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Wilfrid Keller, Prime factors k.2^n + 1 of Fermat numbers F_m
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
Romeo Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv:1202.3670 [math.HO], 2012. - _N. J. A. Sloane_, Jun 13 2012
Romeo Meštrović, Goldbach-type conjectures arising from some arithmetic progressions, University of Montenegro, 2018.
Romeo Meštrović, Goldbach's like conjectures arising from arithmetic progressions whose first two terms are primes, arXiv:1901.07882 [math.NT], 2019.
Salah Eddine Rihane, Chèfiath Awero Adegbindin, and Alain Togbé, Fermat Padovan And Perrin Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.2.
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 65.
Maxie D. Schmidt, New Congruences and Finite Difference Equations for Generalized Factorial Functions, arXiv:1701.04741 [math.CO], 2017.
Bernard Schott, Les nombres brésiliens, Quadrature, no. 76, avril-juin 2010, pages 30-38. Local copy, included here with permission from the editors of Quadrature.
Yaryna Stelmakh, Homeomorphisms of the space of non-zero integers with the Kirch topology, arXiv:2101.04676 [math.GN], 2020.
Eric Weisstein's World of Mathematics, Fermat Number
Eric Weisstein's World of Mathematics, Fermat Prime
Eric Weisstein's World of Mathematics, Pepin's Test
Wikipedia, Fermat number
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016.

Cf. A000215, A001146, A159611, A220627, A220570.
Subsequence of A147545 and of A334101. Cf. also A333788, A334092.
Cf. A045544.

[2^(2^n)+1 : n in [0..4] | IsPrime(2^(2^n)+1)]; // Arkadiusz Wesolowski, Jun 09 2011

Select[Table[2^(2^n) + 1, {n, 0, 4}], PrimeQ] (* Vladimir Joseph Stephan Orlovsky, Apr 29 2008 *)

for(i=0,10, isprime(2^2^i+1) && print1(2^2^i+1,", ")) \\ M. F. Hasler, Nov 21 2009

[2^(2^n)+1 for n in (0..4) if is_prime(2^(2^n)+1)] # G. C. Greubel, Mar 07 2019

a(n+1) = A180024(A049084(a(n))). - Reinhard Zumkeller, Aug 08 2010

a(n) = 1 + A001146(n-1), if 1 <= n <= 5. - Omar E. Pol, Jun 08 2018

A007097 Primeth recurrence: a(n+1) = a(n)-th prime.

Original entry on oeis.org

1, 2, 3, 5, 11, 31, 127, 709, 5381, 52711, 648391, 9737333, 174440041, 3657500101, 88362852307, 2428095424619, 75063692618249, 2586559730396077, 98552043847093519, 4123221751654370051, 188272405179937051081, 9332039515881088707361, 499720579610303128776791, 28785866289100396890228041

Offset: 0

N. J. A. Sloane, Robert G. Wilson v

A007097(n) = Min {k : A109301(k) = n} = the first k whose rote height is n, the level set leader or minimum inverse function corresponding to A109301. - Jon Awbrey, Jun 26 2005
Lubomir Alexandrov informs me that he studied this sequence in his 1965 notebook. - N. J. A. Sloane, May 23 2008
a(n) is the Matula-Goebel number of the rooted path tree on n+1 vertices. The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. - Emeric Deutsch, Feb 18 2012
Conjecture: log(a(1))*log(a(2))*...*log(a(n)) ~ a(n). - Thomas Ordowski, Mar 26 2015

Lubomir Alexandrov, unpublished notes, circa 1960.
L. Longeri, Towards understanding nature and the aesthetics of prime numbers, https://www.longeri.org/prime/nature.html [Broken link, but leave the URL here for historical reasons]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Lubomir Alexandrov, On the nonasymptotic prime number distribution, arXiv:math.NT/9811096, 1998.
Lubomir Alexandrov, "The Eratosthenes Progression p(k+1)=π^{-1}(p(k)), k=0,1,2,..., p(0)=1,4,6,... Determines an Inner Prime Number Distribution Law", Second Int. Conf. "Modern Trends in Computational Physics", Jul 24-29, 2000, Dubna, Russia, Book of Abstracts, p. 19. Available at arXiv:math/0105154 [math.NT], 2001.
Lubomir Alexandrov, Prime Number Sequences And Matrices Generated By Counting Arithmetic Functions, Communications of the Joint Institute of Nuclear Research, E5-2002-55, Dubna, 2002.
J. Awbrey, Riffs and Rotes
R. G. Batchko, A prime fractal and global quasi-self-similar structure in the distribution of prime-indexed primes, arXiv preprint arXiv:1405.2900 [math.GM], 2014.
Peter R. Cappello, A Note on a Bijection between Natural Numbers and Rooted Trees, 4th SIAM Conference on Discrete Mathematics, June 1988. See section 3 set S codes of paths (codes are per Matula-Goebel).
M. Deléglise, Computation of large values of pi(x)
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
Robert G. Wilson v, Letter to N. J. A. Sloane, Sep. 1992
Index entries for sequences related to Matula-Goebel numbers

Row 1 of array A114537.
Left edge of tree A227413, right edge of A246378.
Cf. A000040, A000720, A049076-A049081, A049084, A057450, A109301, A131842, A006450, A292667.
Cf. A078442, A109082 (left inverses).
Subsequence of A245823.

P:=Filtered([1..60000],IsPrime);;
a:=[1];; for n in [2..10] do a[n]:=P[a[n-1]]; od; a; # Muniru A Asiru, Dec 22 2018

a007097 n = a007097_list !! n
a007097_list = iterate a000040 1  -- Reinhard Zumkeller, Jul 14 2013

seq((ithprime@@n)(1),n=0..10); # Peter Luschny, Oct 16 2012

NestList[Prime@# &, 1, 16] (* Robert G. Wilson v, May 30 2006 *)

print1(p=1);until(,print1(","p=prime(p)))  \\ M. F. Hasler, Oct 09 2011

A049084(a(n+1)) = a(n). - Reinhard Zumkeller, Jul 14 2013
a(n)/a(n-1) ~ log(a(n)) ~ prime(n). - Thomas Ordowski, Mar 26 2015
a(n) = prime^{[n]}(1), with the prime function prime(k) = A000040(k), with a(0) = 1. See the name and the programs. - Wolfdieter Lang, Apr 03 2018
Sum_{n>=1} 1/a(n) = A292667. - Amiram Eldar, Oct 15 2020

a(15) corrected and a(16)-a(17) added by Paul Zimmermann
a(18)-a(19) found by David Baugh using a program by Xavier Gourdon and Andrey V. Kulsha, Oct 25 2007
a(20)-a(21) found by Andrey V. Kulsha using a program by Xavier Gourdon, Oct 02 2011
a(22) from Henri Lifchitz, Oct 14 2014
a(23) from David Baugh using Kim Walisch's primecount, May 16 2016

A002476 Primes of the form 6m + 1.

Original entry on oeis.org

7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241, 271, 277, 283, 307, 313, 331, 337, 349, 367, 373, 379, 397, 409, 421, 433, 439, 457, 463, 487, 499, 523, 541, 547, 571, 577, 601, 607, 613, 619

Offset: 1

N. J. A. Sloane

Equivalently, primes of the form 3m + 1.
Rational primes that decompose in the field Q(sqrt(-3)). - N. J. A. Sloane, Dec 25 2017
Primes p dividing Sum_{k=0..p} binomial(2k, k) - 3 = A006134(p) - 3. - Benoit Cloitre, Feb 08 2003
Primes p such that tau(p) == 2 (mod 3) where tau(x) is the Ramanujan tau function (cf. A000594). - Benoit Cloitre, May 04 2003
Primes of the form x^2 + xy - 2y^2 = (x+2y)(x-y). - N. J. A. Sloane, May 31 2014
Primes of the form x^2 - xy + 7y^2 with x and y nonnegative. - T. D. Noe, May 07 2005
Primes p such that p^2 divides Sum_{m=1..2(p-1)} Sum_{k=1..m} (2k)!/(k!)^2. - Alexander Adamchuk, Jul 04 2006
A006512 larger than 5 (Greater of twin primes) is a subsequence of this. - Jonathan Vos Post, Sep 03 2006
A039701(A049084(a(n))) = A134323(A049084(a(n))) = 1. - Reinhard Zumkeller, Oct 21 2007
Also primes p such that the arithmetic mean of divisors of p^2 is an integer: sigma_1(p^2)/sigma_0(p^2) = C. (A000203(p^2)/A000005(p^2) = C). - Ctibor O. Zizka, Sep 15 2008
Fermat knew that these numbers can also be expressed as x^2 + 3y^2 and are therefore not prime in Z[omega], where omega is a complex cubic root of unity. - Alonso del Arte, Dec 07 2012
Primes of the form x^2 + xy + y^2 with x < y and nonnegative. Also see A007645 which also applies when x=y, adding an initial 3. - Richard R. Forberg, Apr 11 2016
For any term p in this sequence, let k = (p^2 - 1)/6; then A016921(k) = p^2. - Sergey Pavlov, Dec 16 2016; corrected Dec 18 2016
For the decomposition p=x^2+3*y^2, x(n) = A001479(n+1) and y(n) = A001480(n+1). - R. J. Mathar, Apr 16 2024

			Since 6 * 1 + 1 = 7 and 7 is prime, 7 is in the sequence. (Also 7 = 2^2 + 3 * 1^2 = (2 + sqrt(-3))(2 - sqrt(-3)).)
Since 6 * 2 + 1 = 13 and 13 is prime, 13 is in the sequence.
17 is prime but it is of the form 6m - 1 rather than 6m + 1, and is therefore not in the sequence.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
David A. Cox, Primes of the Form x^2 + ny^2. New York: Wiley (1989): 8.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 261.

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
C. Banderier, Calcul de (-3/p)
Barry Brent, Finite Field Models of Polynomials Interpolating Fourier Coefficients of Modular Functions for Hecke Groups, Integers (2024) Vol. 24, Art. No. A18. See p. 13.
F. S. Carey, On some cases of the Solutions of the Congruence z^p^(n-1)=1, mod p, Proceedings of the London Mathematical Society, Volume s1-33, Issue 1, November 1900, Pages 294-312.
A. Granville and G. Martin, Prime number races, arXiv:math/0408319 [math.NT], 2004.
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 526.
K. G. Reuschle, Tafeln complexer Primzahlen, Königl. Akademie der Wissenschaften, Berlin, 1875, p. 1.
Neville Robbins, On the Infinitude of Primes of the Form 3k+1, Fib. Q., 43,1 (2005), 29-30.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
Index to sequences related to decomposition of primes in quadratic fields

Cf. A045331, A242660.
For values of m see A024899. Primes of form 3n - 1 give A003627.
These are the primes arising in A024892, A024899, A034936.
A091178 gives prime index.
Cf. A006512, A007528.
Subsequence of A016921 and of A050931.
Cf. A004611 (multiplicative closure).

Filtered(List([0..110],k->6*k+1),n-> IsPrime(n)); # Muniru A Asiru, Mar 11 2019

a002476 n = a002476_list !! (n-1)
a002476_list = filter ((== 1) . (`mod` 6)) a000040_list
-- Reinhard Zumkeller, Jan 15 2013

(#~ 1&p:) >: 6 * i.1000 NB. Stephen Makdisi, May 01 2018

[n: n in [1..700 by 6] | IsPrime(n)]; // Vincenzo Librandi, Apr 05 2011

a := [ ]: for n from 1 to 400 do if isprime(6*n+1) then a := [ op(a), n ]; fi; od: A002476 := n->a[n];

Select[6*Range[100] + 1, PrimeQ[ # ] &] (* Stefan Steinerberger, Apr 06 2006 *)

select(p->p%3==1,primes(100)) \\ Charles R Greathouse IV, Oct 31 2012

From R. J. Mathar, Apr 03 2011: (Start)
Sum_{n >= 1} 1/a(n)^2 = A175644.
Sum_{n >= 1} 1/a(n)^3 = A175645. (End)
a(n) = 6*A024899(n) + 1. - Zak Seidov, Aug 31 2016
From Vaclav Kotesovec, May 02 2020: (Start)
Product_{k>=1} (1 - 1/a(k)^2) = 1/A175646.
Product_{k>=1} (1 + 1/a(k)^2) = A334481.
Product_{k>=1} (1 - 1/a(k)^3) = A334478.
Product_{k>=1} (1 + 1/a(k)^3) = A334477. (End)
Legendre symbol (-3, a(n)) = +1 and (-3, A007528(n)) = -1, for n >= 1. For prime 3 one sets (-3, 3) = 0. - Wolfdieter Lang, Mar 03 2021

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

			From _Gus Wiseman_, May 22 2024: (Start)
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
   30: {1,2,3}
   40: {1,1,1,3}
   54: {1,2,2,2}
   72: {1,1,1,2,2}
   96: {1,1,1,1,1,2}
  128: {1,1,1,1,1,1,1}
(End)

Antti Karttunen, Table of n, a(n) for n = 1..1024
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]

Row 2 of A104244.
Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
The formula section details how the sequence maps the terms of A329050, A329332.
A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
Numbers k such that a(k) is prime are A277319, counts A372688.
Grouping by image gives A277905.
A014499 lists binary indices of prime numbers.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
Binary indices:
- listed A048793, sum A029931
- reversed A272020
- opposite A371572, sum A230877
- length A000120, complement A023416
- min A001511, opposite A000012
- max A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
Cf. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
Cf. A087207, A097248.

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
map(f, [$1..100]); # Robert Israel, Oct 10 2016

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)

a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ Michel Marcus, Oct 10 2016

\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020

from sympy import factorint, primepi
def a(n):
    if n==1: return 0
    f=factorint(n)
    return sum([f[i]*2**(primepi(i) - 1) for i in f])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 19 2017

a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
From Antti Karttunen, Jul 29 2015: (Start)
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
Other identities. For all n >= 0:
a(A019565(n)) = n.
a(A260443(n)) = n.
a(A206296(n)) = A000129(n).
a(A005940(n+1)) = A087808(n).
a(A007913(n)) = A248663(n).
a(A007947(n)) = A087207(n).
a(A283477(n)) = A005187(n).
a(A284003(n)) = A006068(n).
a(A285101(n)) = A028362(1+n).
a(A285102(n)) = A068052(n).
Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016
From Peter Munn, Jan 31 2020: (Start)
a(n^2) = a(A003961(n)) = 2 * a(n).
a(A297845(n,k)) = a(n) * a(k).
a(n) = a(A225546(n)).
a(A329332(n,k)) = n * k.
a(A329050(n,k)) = 2^(n+k).
(End)
From Antti Karttunen, Feb 02-25 2020, Feb 01 2021: (Start)
a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
a(n) = a(A097248(n)).
For n >= 2:
A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
For n >= 1, A331750(n) = a(A000203(n)).
For n >= 1, the following chains hold:
A293447(n) >= a(n) >= A331740(n) >= A331591(n).
a(n) >= A087207(n) >= A248663(n).
(End)
a(n) = A087207(A097248(n)). - Flávio V. Fernandes, Jul 16 2025

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1.

Original entry on oeis.org

1093, 3511

Offset: 1

N. J. A. Sloane

Sequence is believed to be infinite.
Joseph Silverman showed that the abc-conjecture implies that there are infinitely many primes which are not in the sequence. - Benoit Cloitre, Jan 09 2003
Graves and Murty (2013) improved Silverman's result by showing that for any fixed k > 1, the abc-conjecture implies that there are infinitely many primes == 1 (mod k) which are not in the sequence. - Jonathan Sondow, Jan 21 2013
The squares of these numbers are Fermat pseudoprimes to base 2 (A001567) and Catalan pseudoprimes (A163209). - T. D. Noe, May 22 2003
Primes p that divide the numerator of the harmonic number H((p-1)/2); that is, p divides A001008((p-1)/2). - T. D. Noe, Mar 31 2004
In a 1977 paper, Wells Johnson, citing a suggestion from Lawrence Washington, pointed out the repetitions in the binary representations of the numbers which are one less than the two known Wieferich primes; i.e., 1092 = 10001000100 (base 2); 3510 = 110110110110 (base 2). It is perhaps worth remarking that 1092 = 444 (base 16) and 3510 = 6666 (base 8), so that these numbers are small multiples of repunits in the respective bases. Whether this is mathematically significant does not appear to be known. - John Blythe Dobson, Sep 29 2007
A002326((a(n)^2 - 1)/2) = A002326((a(n)-1)/2). - Vladimir Shevelev, Jul 09 2008, Aug 24 2008
It is believed that p^2 does not divide 3^(p-1) - 1 if p = a(n). This is true for n = 1 and 2. See A178815, A178844, A178900, and Ostafe-Shparlinski (2010) Section 1.1. - Jonathan Sondow, Jun 29 2010
These primes also divide the numerator of the harmonic number H(floor((p-1)/4)). - H. Eskandari (hamid.r.eskandari(AT)gmail.com), Sep 28 2010
1093 and 3511 are prime numbers p satisfying congruence 429327^(p-1) == 1 (mod p^2). Why? - Arkadiusz Wesolowski, Apr 07 2011. Such bases are listed in A247208. - Max Alekseyev, Nov 25 2014. See A269798 for all such bases, prime and composite, that are not powers of 2. - Felix Fröhlich, Apr 07 2018
A196202(A049084(a(1))) = A196202(A049084(a(2))) = 1. - Reinhard Zumkeller, Sep 29 2011
If q is prime and q^2 divides a prime-exponent Mersenne number, then q must be a Wieferich prime. Neither of the two known Wieferich primes divide Mersenne numbers. See Will Edgington's Mersenne page in the links below. - Daran Gill, Apr 04 2013
There are no other terms below 4.97*10^17 as established by PrimeGrid (see link below). - Max Alekseyev, Nov 20 2015. The search was done via PrimeGrid's PRPNet and the results were not double-checked. Because of the unreliability of the testing, the search was suspended in May 2017 (cf. Goetz, 2017). - Felix Fröhlich, Apr 01 2018. On Nov 28 2020, PrimeGrid has resumed the search (cf. Reggie, 2020). - Felix Fröhlich, Nov 29 2020. As of Dec 29 2022, PrimeGrid has completed the search to 2^64 (about 1.8 * 10^19) and has no plans to continue further. - Charles R Greathouse IV, Sep 24 2024
Are there other primes q >= p such that q^2 divides 2^(p-1)-1, where p is a prime? - Thomas Ordowski, Nov 22 2014. Any such q must be a Wieferich prime. - Max Alekseyev, Nov 25 2014
Primes p such that p^2 divides 2^r - 1 for some r, 0 < r < p. - Thomas Ordowski, Nov 28 2014, corrected by Max Alekseyev, Nov 28 2014
For some reason, both p=a(1) and p=a(2) also have more bases b with 1 < b < p that make b^(p-1) == 1 (mod p^2) than any smaller prime p; in other words, a(1) and a(2) belong to A248865. - Jeppe Stig Nielsen, Jul 28 2015
Let r_1, r_2, r_3, ..., r_i be the set of roots of the polynomial X^((p-1)/2) - (p-3)! * X^((p-3)/2) - (p-5)! * X^((p-5)/2) - ... - 1. Then p is a Wieferich prime iff p divides sum{k=1, p}(r_k^((p-1)/2)) (see Example 2 in Jakubec, 1994). - Felix Fröhlich, May 27 2016
Arthur Wieferich showed that if p is not a term of this sequence, then the First Case of Fermat's Last Theorem has no solution in x, y and z for prime exponent p (cf. Wieferich, 1909). - Felix Fröhlich, May 27 2016
Let U_n(P, Q) be a Lucas sequence of the first kind, let e be the Legendre symbol (D/p) and let p be a prime not dividing 2QD, where D = P^2 - 4*Q. Then a prime p such that U_(p-e) == 0 (mod p^2) is called a "Lucas-Wieferich prime associated to the pair (P, Q)". Wieferich primes are those Lucas-Wieferich primes that are associated to the pair (3, 2) (cf. McIntosh, Roettger, 2007, p. 2088). - Felix Fröhlich, May 27 2016
Any repeated prime factor of a term of A000215 is a term of this sequence. Thus, if there exist infinitely many Fermat numbers that are not squarefree, then this sequence is infinite, since no two Fermat numbers share a common factor. - Felix Fröhlich, May 27 2016
If the Diophantine equation p^x - 2^y = d has more than one solution in positive integers (x, y), with (p, d) not being one of the pairs (3, 1), (3, -5), (3, -13) or (5, -3), then p is a term of this sequence (cf. Scott, Styer, 2004, Corollary to Theorem 2). - Felix Fröhlich, Jun 18 2016
Odd primes p such that Chi_(D_0)(p) != 1 and Lambda_p(Q(sqrt(D_0))) != 1, where D_0 < 0 is the fundamental discriminant of the imaginary quadratic field Q(sqrt(1-p^2)) and Chi and Lambda are Iwasawa invariants (cf. Byeon, 2006, Proposition 1 (i)). - Felix Fröhlich, Jun 25 2016
If q is an odd prime, k, p are primes with p = 2*k+1, k == 3 (mod 4), p == -1 (mod q) and p =/= -1 (mod q^3) (Jakubec, 1998, Corollary 2 gives p == -5 (mod q) and p =/= -5 (mod q^3)) with the multiplicative order of q modulo k = (k-1)/2 and q dividing the class number of the real cyclotomic field Q(Zeta_p + (Zeta_p)^(-1)), then q is a term of this sequence (cf. Jakubec, 1995, Theorem 1). - Felix Fröhlich, Jun 25 2016
From Felix Fröhlich, Aug 06 2016: (Start)
Primes p such that p-1 is in A240719.
Prime terms of A077816 (cf. Agoh, Dilcher, Skula, 1997, Corollary 5.9).
p = prime(n) is in the sequence iff T(2, n) > 1, where T = A258045.
p = prime(n) is in the sequence iff an integer k exists such that T(n, k) = 2, where T = A258787. (End)
Conjecture: an integer n > 1 such that n^2 divides 2^(n-1)-1 must be a Wieferich prime. - Thomas Ordowski, Dec 21 2016
The above conjecture is equivalent to the statement that no "Wieferich pseudoprimes" (WPSPs) exist. While base-b WPSPs are known to exist for several bases b > 1 other than 2 (see for example A244752), no base-2 WPSPs are known. Since two necessary conditions for a composite to be a base-2 WPSP are that, both, it is a base-2 Fermat pseudoprime (A001567) and all its prime factors are Wieferich primes (cf. A270833), as shown in the comments in A240719, it seems that the first base-2 WPSP, if it exists, is probably very large. This appears to be supported by the guess that the properties of a composite to be a term of A001567 and of A270833 are "independent" of each other and by the observation that the scatterplot of A256517 seems to become "less dense" at the x-axis parallel line y = 2 for increasing n. It has been suggested in the literature that there could be asymptotically about log(log(x)) Wieferich primes below some number x, which is a function that grows to infinity, but does so very slowly. Considering the above constraints, the number of WPSPs may grow even more slowly, suggesting any such number, should it exist, probably lies far beyond any bound a brute-force search could reach in the forseeable future. Therefore I guess that the conjecture may be false, but a disproof or the discovery of a counterexample are probably extraordinarily difficult problems. - Felix Fröhlich, Jan 18 2019
Named after the German mathematician Arthur Josef Alwin Wieferich (1884-1954). a(1) = 1093 was found by Waldemar Meissner in 1913. a(2) = 3511 was found by N. G. W. H. Beeger in 1922. - Amiram Eldar, Jun 05 2021
From Jianing Song, Jun 21 2025: (Start)
The ring of integers of Q(2^(1/k)) is Z[2^(1/k)] if and only if k does not have a prime factor in this sequence (k is in A342390). See Theorem 5.3 of the paper of Keith Conrad. For example, we have:
  (1 + 2^(364/1093) + 2^(2*364/1093) + ... + 2^(1092*364/1093))/1093 is an algebraic integer, but it is not in Z[2^(1/1093)];
  (1 + 2^(1755/3511) + 2^(2*1755/3511) + ... + 2^(3510*1755/3511))/3511 is an algebraic integer, but it is not in Z[2^(1/3511)]. (End)

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 28.
Richard K. Guy, Unsolved Problems in Number Theory, A3.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 91.
Yves Hellegouarch, "Invitation aux mathématiques de Fermat Wiles", Dunod, 2eme Edition, pp. 340-341.
Pace Nielsen, Wieferich primes, heuristics, computations, Abstracts Amer. Math. Soc., 33 (#1, 20912), #1077-11-48.
Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 263.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 230-234.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, NY, 1986, p. 163.

Takashi Agoh, Karl Dilcher and Ladislav Skula, Fermat Quotients for Composite Moduli, Journal of Number Theory 66(1), 1997, 29-50.
Joerg Arndt, Matters Computational (The Fxtbook), p. 780.
Alex Samuel Bamunoba, A note on Carlitz Wieferich primes, Journal of Number Theory, Vol. 174 (2017), pp. 343-357;
N. G. W. H. Beeger, On a New Case of the Congruence 2^(p-1) == 1 (mod p^2), Messenger of Mathematics, Vol 51 (1922), pp. 149-150.
Dongho Byeon, Class numbers, Iwasawa invariants and modular forms, Trends in Mathematics, Vol. 9, No. 1, (2006), pp. 25-29.
Chris K. Caldwell, The Prime Glossary, Wieferich prime.
Chris K. Caldwell, Prime-square Mersenne divisors are Wieferich.
Denis Xavier Charles, On Wieferich Primes.
Keith Conrad, The ring of integers in a radical extension.
Richard Crandall, Karl Dilcher and Carl Pomerance, A search for Wieferich and Wilson primes, Mathematics of Computation, Vol. 66, No. 217 (1997), pp. 433-449; alternative link.
Joe K. Crump, Joe's Number Theory Web, Weiferich Primes. (sic)
John Blythe Dobson, A note on the two known Wieferich Primes, 2007-2015.
John Blythe Dobson A Characterization of Wilson-Lerch Primes, Integers, Vol. 16 (2016), A51.
John Blythe Dobson, On the special harmonic numbers H_floor(p/9) and H_floor(p/18) modulo p, arXiv:2302.02027 [math.NT], 2023.
F. G. Dorais, WPSE - A Wieferich Prime Search Engine (A program to search Wieferich primes written by F. G. Dorais.) - _Felix Fröhlich_, Jul 13 2014
François G. Dorais and Dominic W. Klyve, A Wieferich Prime Search up to 6.7*10^15, Journal of Integer Sequences, Vol. 14 (2011), Article 11.9.2.
Bruno Dular, Cycles of Sums of Integers, arXiv:1905.01765 [math.NT], 2019.
Will Edgington, Mersenne Page [from Internet Archive Wayback Machine].
M. Goetz, WSS and WFS are suspended, PrimeGrid forum, Message 107809, May 11, 2017.
Andrew Granville and K. Soundararajan, A binary additive problem of Erdős and the order of 2 mod p^2, Raman. J., Vol. 2 (1998) pp. 283-298
Hester Graves and M. Ram Murty, The abc conjecture and non-Wieferich primes in arithmetic progressions, Journal of Number Theory, Vol. 133 (2013), pp. 1809-1813.
René Gy, Extended Congruences for Harmonic Numbers, arXiv:1902.05258 [math.NT], 2019.
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (ps, pdf)
Stanislav Jakubec, Connection between the Wieferich congruence and divisibility of h+, Acta Arithmetica, Vol. 71, No. 1 (1995), pp. 55-64.
Stanislav Jakubec, On divisibility of the class number h+ of the real cyclotomic fields of prime degree l, Mathematics of Computation, Vol. 67, No. 221 (1998), pp. 369-398.
Stanislav Jakubec, The Congruence for Gauss Period, Journal of Number Theory, Vol. 48, No. 1 (1994), pp. 36-45.
Wells Johnson, On the nonvanishing of Fermat quotients (mod p), Journal f. die reine und angewandte Mathematik, Vol. 292, (1977), pp. 196-200.
Jiří Klaška, A Simple Proof of Skula's Theorem on Prime Power Divisors of Mersenne Numbers, J. Int. Seq., Vol. 25 (2022), Article 22.4.3.
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
Joshua Knauer and Jörg Richstein, The continuing search for Wieferich primes, Math. Comp., Vol. 74, No. 251 (2005), pp. 1559-1563.
D. H. Lehmer, On Fermat's quotient, base two, Math. Comp., Vol. 36, No. 153 (1981), pp. 289-290.
Richard J. McIntosh and Eric L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp., Vol 76, No. 260 (2007), pp. 2087-2094.
C. McLeman, PlanetMath.org, Wieferich prime.
Waldemar Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Berlin, Vol. 35 (1913), pp. 663-667. [Annotated scanned copy]
Sihem Mesnager and Jean-Pierre Flori, A note on hyper-bent functions via Dillon-like exponents, IACR, Report 2012/033, 2012.
Mishima Miwako and Koji Momihara, A new series of optimal tight conflict-avoiding codes of weight 3, Discrete Mathematics, Vol. 340, No. 4 (2017), pp. 617-629. See page 618.
Alina Ostafe and Igor E. Shparlinski, Pseudorandomness and Dynamics of Fermat Quotients, arXiv:1001.1504 [math.NT], 2010.
Christian Perfect, Integer sequence reviews on Numberphile (or vice versa), 2013.
Reggie, Welcome to the Wieferich and Wall-Sun-Sun Prime Search, PrimeGrid forum, 2020.
Reese Scott and Robert Styer, On p^x - q^y = c and related three term exponential Diophantine equations with prime bases, Journal of Number Theory, Vol. 105, No. 2 (2004), pp. 212-234.
Vladimir Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arXiv:0806.3412 [math.NT], 2008.
Joseph Silverman, Wieferich's Criterion and the abc Conjecture, J. Number Th. 30 (1988) 226-237.
Jonathan Sondow, Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771, arXiv:1110.3113 [math.NT], 2012.
Jonathan Sondow, Lerch Quotients, Lerch Primes, Fermat-Wilson Quotients, and the Wieferich-non-Wilson Primes 2, 3, 14771, Combinatorial and Additive Number Theory, CANT 2011 and 2012, Springer Proc. in Math. & Stat., Vol. 101 (2014), pp. 243-255.
Michel Waldschmidt, Lecture on the abc conjecture and some of its consequences, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.
Michel Waldschmidt, Lecture on the abc conjecture and some of its consequences, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.
Eric Weisstein's World of Mathematics, Wieferich Prime.
Eric Weisstein's World of Mathematics, abc Conjecture.
Eric Weisstein's World of Mathematics, Integer Sequence Primes.
A. Wieferich, Zum letzten Fermat'schen Theorem, Journal für die reine und angewandte Mathematik, Vol. 136 (1909), pp. 293-302.
Wikipedia, Wieferich prime.
Paul Zimmermann, Records for Prime Numbers.

Cf. similar primes related to the first case of Fermat's last theorem: A007540, A088164.
Sequences "primes p such that p^2 divides X^(p-1)-1": A014127 (X=3), A123692 (X=5), A212583 (X=6), A123693 (X=7), A045616 (X=10), A111027 (X=12), A128667 (X=13), A234810 (X=14), A242741 (X=15), A128668 (X=17), A244260 (X=18), A090968 (X=19), A242982 (X=20), A298951 (X=22), A128669 (X=23), A306255 (X=26), A306256 (X=30).
Cf. A001567, A002323, A077816, A001008, A039951, A049094, A126196, A126197, A178815, A178844, A178871, A178900, A246503, A247208, A269798.

Filtered([1..50000],p->IsPrime(p) and (2^(p-1)-1) mod p^2 =0); # Muniru A Asiru, Apr 03 2018

import Data.List (elemIndices)
a001220 n = a001220_list !! (n-1)
a001220_list = map (a000040 . (+ 1)) $ elemIndices 1 a196202_list
-- Reinhard Zumkeller, Sep 29 2011

[p : p in PrimesUpTo(310000) | IsZero((2^(p-1) - 1) mod (p^2))]; // Vincenzo Librandi, Jan 19 2019

wieferich := proc (n) local nsq, remain, bin, char: if (not isprime(n)) then RETURN("not prime") fi: nsq := n^2: remain := 2: bin := convert(convert(n-1, binary),string): remain := (remain * 2) mod nsq: bin := substring(bin,2..length(bin)): while (length(bin) > 1) do: char := substring(bin,1..1): if char = "1" then remain := (remain * 2) mod nsq fi: remain := (remain^2) mod nsq: bin := substring(bin,2..length(bin)): od: if (bin = "1") then remain := (remain * 2) mod nsq fi: if remain = 1 then RETURN ("Wieferich prime") fi: RETURN ("non-Wieferich prime"): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 01 2001

Select[Prime[Range[50000]],Divisible[2^(#-1)-1,#^2]&]  (* Harvey P. Dale, Apr 23 2011 *)
Select[Prime[Range[50000]],PowerMod[2,#-1,#^2]==1&] (* Harvey P. Dale, May 25 2016 *)

N=10^4; default(primelimit,N);
forprime(n=2,N,if(Mod(2,n^2)^(n-1)==1,print1(n,", ")));
\\ Joerg Arndt, May 01 2013

from sympy import prime
from gmpy2 import powmod
A001220_list = [p for p in (prime(n) for n in range(1,10**7)) if powmod(2,p-1,p*p) == 1]
# Chai Wah Wu, Dec 03 2014

(A178815(A000720(p))^(p-1) - 1) mod p^2 = A178900(n), where p = a(n). - Jonathan Sondow, Jun 29 2010

Odd primes p such that A002326((p^2-1)/2) = A002326((p-1)/2). See A182297. - Thomas Ordowski, Feb 04 2014

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).

Each n occurs A000081(n) times.

			a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.

import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
   g x = y : g (x + 1) where
      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
          where t = a049084 x; u = a020639 x; v = x `div` u
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
a(n) = A091238(A091204(n)). - Antti Karttunen, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

cp's OEIS Frontend

A061395 Let p be the largest prime factor of n; if p is the k-th prime then set a(n) = k; a(1) = 0 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A064989 Multiplicative with a(2^e) = 1 and a(p^e) = prevprime(p)^e for odd primes p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A003963 Fully multiplicative with a(p) = k if p is the k-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A055396 Smallest prime dividing n is a(n)-th prime (a(1)=0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A019434 Fermat primes: primes of the form 2^(2^k) + 1, for some k >= 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage