A004280 -id:A004280 - cp's OEIS frontend

A368382 a(1) = 1; for n > 1, a(n) is the least positive integer not already in the sequence such that a(n) == a(n-1) (mod A004280(n)).

1, 3, 6, 11, 4, 13, 2, 15, 30, 47, 9, 51, 5, 55, 28, 57, 26, 59, 24, 61, 22, 63, 20, 65, 18, 67, 16, 69, 14, 71, 12, 73, 10, 75, 8, 77, 148, 221, 146, 223, 144, 225, 142, 227, 53, 231, 49, 235, 45, 239, 41, 243, 37, 247, 33, 251, 29, 255, 25, 259, 21, 263, 17, 267, 140, 269, 7, 273, 138, 275, 136, 277, 134, 279, 132, 281

Offset: 1

N. J. A. Sloane, Mar 03 2024

nonn

Analogous to A364054, but whereas that sequence is based on the sequence of primes (2, 3, 5, 7, 11, ....), the present sequence is based on the sequence 2, 3, 5, 7, 9, 11, 13, 15, ... (2 together with the odd numbers >1, essentially A004280).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A004280.

Similar definitions: A005132, A006509, A364054.

from itertools import count, islice
def A368382_gen(): # generator of terms
    a, aset, p = 1, {0,1}, 2
    while True:
        yield a
        for b in count(a%p,p):
            if b not in aset:
                aset.add(b)
                a, p = b, 3 if p == 2 else p+2
                break
A368382_list = list(islice(A368382_gen(),40)) # Chai Wah Wu, Mar 05 2024

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)

A002858 Ulam numbers: a(1) = 1; a(2) = 2; for n>2, a(n) = least number > a(n-1) which is a unique sum of two distinct earlier terms.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339

Offset: 1

N. J. A. Sloane

Ulam conjectured that this sequence has density 0. However, calculations up to 6.759*10^8 (Jud McCranie) indicate that the density hovers near 0.074.
A plot of the first 3 million terms shows that they lie very close to the straight line 13.51*n, so even if we cannot prove it, we believe we now know how this sequence grows (see the plots in the links below). - N. J. A. Sloane, Sep 27 2006
After a few initial terms, the sequence settles into a regular pattern of dense clumps separated by sparse gaps, with period 21.601584+. This pattern continues up to at least a(n) = 5*10^6. (This comment is just a qualitative statement about the wavelike distribution of Ulam numbers, not meant to imply that every period includes Ulam numbers.) - David W. Wilson
_Don Knuth_ (Sep 26 2006) remarks that a(4952)=64420 and a(4953)=64682 (a gap of more than ten "dense clumps"); and there is a gap of 315 between a(18857) and a(18858).
1,2,3,47 are the only values of x < 6.759*10^8 such that x and x+1 are both Ulam numbers. - Jud McCranie, Jun 08 2001.  This holds through the first 28 billion Ulam numbers - Jud McCranie, Jan 07 2016.
From Jud McCranie on David W. Wilson's illustration, Jun 20 2008: (Start)
The integers are shown from left to right, top to bottom, with a dot where there is an Ulam number. I think his plot is 216 wide. The local density of Ulam numbers goes in waves with a period of 21.6+, so his plot shows ten cycles.
When they are arranged that way you can see the waves. The crests of the density waves don't always have Ulam numbers there but the troughs are practically void of Ulam numbers. I noticed that the ratio of that period (21.6+) to the frequency of Ulam numbers (1 in 13.52) is very close to 8/5. (End)
a(50000000) = 675904508. - Jud McCranie, Feb 29 2012
a(100000000) = 1351856726. - Jud McCranie, Jul 31 2012
a(1000000000) = 13517664323. - Jud McCranie, Aug 28 2015
a(28000000000) = 378485625853 - Philip Gibbs & Jud McCranie, Sep 09 2015
3 (=1+2) and 131 (=62+69) are the only two Ulam numbers in the first 28 billion Ulam numbers that are the sum of two consecutive Ulam numbers. - Jud McCranie, Jan 09 2016
Named after the Polish-American scientist Stanislaw Ulam (1909-1984). - Amiram Eldar, Jun 08 2021

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.2.
Richard K. Guy, Unsolved Problems in Number Theory, C4.
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.3.
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 116.
Marvin C. Wunderlich, The improbable behavior of Ulam's summation sequence, pp. 249-257 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
David Zeitlin, Ulam's sequence {U_n}, U_1=1, U_2=2, is a complete sequence, Notices Amer. Math. Soc., 22 (No. 7, 1975), Abstract 75T-A267, p. A-707.

Jud McCranie, Table of n, a(n) for n = 1..10000
Richard A. Becker, Plot of residuals a(n) - 13.5167*n for n <= 3000000, postscript file [uses Jud McCranie's values of a(n)].
Richard A. Becker, Plot of residuals a(n) - 13.5167*n for n <= 3000000, pdf file [uses Jud McCranie's values of a(n)].
Thomas Bloom, Problem 342, Erdős Problems.
Henning Fernau and Kshitij Gajjar, The Space Complexity of Sum Labelling, arXiv:2107.12973 [cs.DS], 2021.
Steven R. Finch, Ulam s-Additive Sequences. [From Steven Finch, Apr 20 2019]
Steven R. Finch, Stolarsky-Harborth Constant.
Steven R. Finch, Stolarsky-Harborth Constant. [From the Wayback machine]
Philip Gibbs, An Efficient Way to Compute Ulam Numbers.
Philip Gibbs, A Conjecture for Ulam Sequences.
Philip Gibbs and Judson McCranie, The Ulam Numbers up to One Trillion, (2017).
Shyam Sunder Gupta, Ulam Numbers. In: Exploring the Beauty of Fascinating Numbers. Springer Praxis Books(). Springer, Singapore, (2025).
Alois P. Heinz, Ulam spiral of Ulam numbers.
Donald E. Knuth, Downloadable programs
Noah Kravitz and Stefan Steinerberger, Ulam Sequences and Ulam Sets, arXiv:1705.01883 [math.CO], 2017.
Borys Kuca, Structures in Additive Sequences, arXiv:1804.09594 [math.NT], 2018. See p. 3.
Jud McCranie, Density 10^2 to 10^12
Jud McCranie, Density 10^4 to 10^12
Jud McCranie, Density 10^6 to 10^12
J. W. Moon, R. K. Guy, and N. J. A. Sloane, Correspondence, 1973.
Ed Pegg, Jr., Graph of 10^6 terms of a(n) - 13.5*n.
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #8. [Annotated and scanned copy]
R. Queneau, Sur les suites s-additives, J. Combin. Theory, A12 (1972), 31-71.
Bernardo Recamán, Questions on a sequence of Ulam, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 919-920.
Ivano Salvo and Agnese Pacifico, Computing Integer Sequences: Filtering vs Generation (Functional Pearl), arXiv:1807.11792 [cs.PL], 2018.
James Schmerl and Eugene Spiegel, The regularity of some 1-additive sequences, J. Combin. Theory. Ser. A, Vol. 66, No. 1 (1994), pp. 172-175. Math. Rev. 95h:11010.
Arseniy Sheydvasser, The Ulam Sequence of the Integer Polynomial Ring, arXiv:1910.00109 [math.NT], 2019.
N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970 (note that A1148 has now become A005282).
Arseniy (Senia) Sheydvasser, The Ulam Sequence of Linear Integer Polynomials, J. Int. Seq., Vol. 24 (2021), Article 21.10.8.
Stefan Steinerberger, A hidden signal in the Ulam sequence, Research Report YALEU/DCS/TR-1508, Yale University, 2015.
Stefan Steinerberger, A hidden signal in the Ulam sequence, Figure 2 from Research Report YALEU/DCS/TR-1508, Yale University, 2015.
Stefan Steinerberger, The Ulam Sequence, blog post, April 12, 2016.
Stanislaw M. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962 [Annotated scanned copy]
Stanislaw Ulam, Combinatorial analysis in infinite sets and some physical theories, SIAM Rev., Vol. 6, No. 4 (1964), pp. 343-355. Reprinted in Selected Papers, MIT Press, see p. 393.
Eric Weisstein's World of Mathematics, Ulam Sequence.
Wikipedia, Ulam number.
David W. Wilson, Plot of initial terms, showing their quasiperiodicity as vertical bars. The image width was chosen to include approximately 10 periods. For an explanation of this picture, see Comments above.
Robert G. Wilson v, Letter to N. J. A. Sloane, Sep. 1992.
David Zeitlin, Ulam's sequence {U_n}, U_1=1, U_2=2, is a complete sequence, Notices Amer. Math. Soc., 22 (No. 7, 1975), Abstract 75T-A267, p. A-707. (Annotated scanned copy)
Index entries for Ulam numbers

Cf. A002859 (version beginning 1,3), A054540, A003667, A001857, A007300, A117140, A214603.
First differences: A072832, A072540.
Cf. A080287, A080288, A004280 (if distinct removed from definition).
Cf. A199016, A199017, A033629, A274522.
See also the density plots in A080573 and A285884.

a002858 n = a002858_list !! (n-1)
a002858_list = 1 : 2 : ulam 2 2 a002858_list
ulam :: Int -> Integer -> [Integer] -> [Integer]
ulam n u us = u' : ulam (n + 1) u' us where
   u' = f 0 (u+1) us'
   f 2 z _                         = f 0 (z + 1) us'
   f e z (v:vs) | z - v <= v       = if e == 1 then z else f 0 (z + 1) us'
                | z - v `elem` us' = f (e + 1) z vs
                | otherwise        = f e z vs
   us' = take n us
-- Reinhard Zumkeller, Nov 03 2011

function isUlam(u, n, h, i, r)
    h == 2 && return false
    ur = u[r]; ui = u[i]
    ur <= ui && return h == 1
    if ur + ui > n
        r -= 1
    elseif ur + ui < n
        i += 1
    else
        h += 1; i += 1; r -= 1
    end
    isUlam(u, n, h, i, r)
end
function UlamList(len)
    u = Array{Int, 1}(undef, len)
    u[1] = 1; u[2] = 2; i = 2; n = 2
    while i < len
        n += 1
        if isUlam(u, n, 0, 1, i)
            i += 1
            u[i] = n
        end
    end
    return u
end
println(UlamList(59)) # Peter Luschny, Apr 07 2019

UlamList := proc(len) local isUlam, nextUlam, behead; behead := u -> u[2..numelems(u)]; isUlam := proc(n, h, u, r) local hu, tu, hr, tr; hu := u[1]; hr := r[1]; if h = 2 then return false fi; if hr <= hu then return evalb(h = 1) fi; if (hr + hu) = n then tu := behead(u); tr := behead(r); return isUlam(n, h+1, tu, tr) fi; if (hr + hu) < n then tu := behead(u): return isUlam(n, h, tu, r) fi; tr := behead(r); isUlam(n, h, u, tr) end: nextUlam := proc(n, u, r) if isUlam(n, 0, u, r) then if nops(u) = len-1 then return [op(u), n] fi; nextUlam(n+1, [op(u), n], [n, op(r)]) else nextUlam(n+1, u, r) fi end: nextUlam(3, [1, 2], [2, 1]) end:
UlamList(59); # Peter Luschny, Apr 05 2019

Ulam4Compiled = Compile[{{nmax, _Integer}, {init, _Integer, 1}, {s, _Integer}}, Module[{ulamhash = Table[0, {nmax}], ulam = init}, ulamhash[[ulam]] = 1; Do[ If[Quotient[Plus @@ ulamhash[[i - ulam]], 2] == s, AppendTo[ulam, i]; ulamhash[[i]] = 1], {i, Last[init] + 1, nmax}]; ulam]]; ulams = Ulam4Compiled[355, {1, 2}, 1]
(* Second program: *)
ulams = {1, 2}; Do[AppendTo[ulams, n = Last[ulams]; While[n++; Length[DeleteCases[Intersection[ulams, n - ulams], n/2, 1, 1]] != 2]; n], {100}]; ulams (* Jean-François Alcover, Sep 08 2011 *)
findUlams[s_List, j_Integer] := Block[{k = s[[-1]] + 1, ss = Plus @@@ Subsets[s, {j}]}, While[ Count[ss, k] != 1, k++]; Append[s, k]]; ulams = Nest[findUlams[#, 2] &, {1, 2}, 70] (* Robert G. Wilson v, Jul 05 2014 *)

aupto(N)= my(seen=vector(N), U=[]); seen[1]=seen[2]=1; for(i=1,N, if(1==seen[i], for(j=1,#U, my(sum=i+U[j]); if(sum>N, break); seen[sum]++); U=concat(U,i))); U \\ Ruud H.G. van Tol, Dec 29 2022

def isUlam(n, h, u, r):
    if h == 2: return False
    hu = u[0]; hr = r[0]
    if hr <= hu: return h == 1
    if hr + hu > n: r = r[1:]
    elif hr + hu < n: u = u[1:]
    else: h += 1; r = r[1:]; u = u[1:]
    return isUlam(n, h, u, r)
def UlamList(length):
    u = [1, 2]; r = [2, 1]; n = 2
    while len(u) < length:
        n += 1
        if isUlam(n, 0, u[:], r[:]):
            u.append(n); r.insert(0, n)
    return u
print(UlamList(59)) # Peter Luschny, Apr 06 2019

More terms from Jud McCranie

A083221 Sieve of Eratosthenes arranged as an array and read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

2, 4, 3, 6, 9, 5, 8, 15, 25, 7, 10, 21, 35, 49, 11, 12, 27, 55, 77, 121, 13, 14, 33, 65, 91, 143, 169, 17, 16, 39, 85, 119, 187, 221, 289, 19, 18, 45, 95, 133, 209, 247, 323, 361, 23, 20, 51, 115, 161, 253, 299, 391, 437, 529, 29, 22, 57, 125, 203, 319, 377, 493, 551, 667

Offset: 2

Yasutoshi Kohmoto, Jun 05 2003

This is permutation of natural numbers larger than 1.
From Antti Karttunen, Dec 19 2014: (Start)
If we assume here that a(1) = 1 (but which is not explicitly included because outside of the array), then A252460 gives an inverse permutation. See also A249741.
For navigating in this array:
A055396(n) gives the row number of row where n occurs, and A078898(n) gives its column number, both starting their indexing from 1.
A250469(n) gives the number immediately below n, and when n is an odd number >= 3, A250470(n) gives the number immediately above n. If n is a composite, A249744(n) gives the number immediately left of n.
First cube of each row, which is {the initial prime of the row}^3 and also the first number neither a prime or semiprime, occurs on row n at position A250474(n).
(End)
The n-th row contains the numbers whose least prime factor is the n-th prime: A020639(T(n,k)) = A000040(n). - Franklin T. Adams-Watters, Aug 07 2015

			The top left corner of the array:
   2,   4,   6,    8,   10,   12,   14,   16,   18,   20,   22,   24,   26
   3,   9,  15,   21,   27,   33,   39,   45,   51,   57,   63,   69,   75
   5,  25,  35,   55,   65,   85,   95,  115,  125,  145,  155,  175,  185
   7,  49,  77,   91,  119,  133,  161,  203,  217,  259,  287,  301,  329
  11, 121, 143,  187,  209,  253,  319,  341,  407,  451,  473,  517,  583
  13, 169, 221,  247,  299,  377,  403,  481,  533,  559,  611,  689,  767
  17, 289, 323,  391,  493,  527,  629,  697,  731,  799,  901, 1003, 1037
  19, 361, 437,  551,  589,  703,  779,  817,  893, 1007, 1121, 1159, 1273
  23, 529, 667,  713,  851,  943,  989, 1081, 1219, 1357, 1403, 1541, 1633
  29, 841, 899, 1073, 1189, 1247, 1363, 1537, 1711, 1769, 1943, 2059, 2117
  ...

Transpose of A083140.
One more than A249741.
Inverse permutation: A252460.
Column 1: A000040, Column 2: A001248.
Row 1: A005843, Row 2: A016945, Row 3: A084967, Row 4: A084968, Row 5: A084969, Row 6: A084970.
Main diagonal: A083141.
First semiprime in each column occurs at A251717; A251718 & A251719 with additional criteria. A251724 gives the corresponding semiprimes for the latter. See also A251728.
Permutations based on mapping numbers between this array and A246278: A249817, A249818, A250244, A250245, A250247, A250249. See also: A249811, A249814, A249815.
Also used in the definition of the following arrays of permutations: A249821, A251721, A251722.
Cf. A002260, A004736, A004280, A020639, A038179, A055396, A078898, A138511, A249820, A249730, A249735, A249744, A250469, A250470, A250472, A250474.

lim = 11; a = Table[Take[Prime[n] Select[Range[lim^2], GCD[# Prime@ n, Product[Prime@ i, {i, 1, n - 1}]] == 1 &], lim], {n, lim}]; Flatten[Table[a[[i, n - i + 1]], {n, lim}, {i, n}]] (* Michael De Vlieger, Jan 04 2016, after Yasutoshi Kohmoto at A083140 *)

More terms from Hugo Pfoertner, Jun 13 2003

A002559 Markoff (or Markov) numbers: union of positive integers x, y, z satisfying x^2 + y^2 + z^2 = 3xy*z.

Original entry on oeis.org

1, 2, 5, 13, 29, 34, 89, 169, 194, 233, 433, 610, 985, 1325, 1597, 2897, 4181, 5741, 6466, 7561, 9077, 10946, 14701, 28657, 33461, 37666, 43261, 51641, 62210, 75025, 96557, 135137, 195025, 196418, 294685, 426389, 499393, 514229, 646018, 925765, 1136689, 1278818

Offset: 1

N. J. A. Sloane and J. H. Conway

A004280 gives indices of Fibonacci numbers (A000045) which are also Markoff (or Markov) numbers.
As mentioned by Conway and Guy, all odd-indexed Pell numbers (A001653) also appear in this sequence. The positions of the Fibonacci and Pell numbers in this sequence are given in A158381 and A158384, respectively. - T. D. Noe, Mar 19 2009
Assuming that each solution (x,y,z) is ordered x <= y <= z, the open problem is to prove that each z value occurs only once. There are no counterexamples in the first 1046858 terms, which have z values < Fibonacci(5001) = 6.2763...*10^1044. - T. D. Noe, Mar 19 2009
Zagier shows that there are C log^2 (3x) + O(log x (log log x)^2) Markoff numbers below x, for C = 0.180717.... - Charles R Greathouse IV, Mar 14 2010 [but see Thompson, below]
The odd numbers in this sequence are of the form 4k+1. - Paul Muljadi, Jan 31 2011
All prime divisors of Markov numbers (with exception 2) are of the form 4k+1. - Artur Jasinski, Nov 20 2011
Kaneko extends a parameterization of Markoff numbers, citing Frobenius, and relates it to a conjectured behavior of the elliptic modular j-function at real quadratic numbers. - Jonathan Vos Post, May 06 2012
Riedel (2012) claims a proof of the unicity conjecture: "it will be shown that the largest member of [a Markoff] triple determines the other two uniquely." - Jonathan Sondow, Aug 21 2012
There are 93 terms with each term <= 2*10^9 in the sequence. The number of distinct prime divisors of any of the first 93 terms is less than 6. The second, third, 4th, 5th, 6th, 10th, 11th, 15th, 16th, 18th, 20th, 24th, 25th, 27th, 30th, 36th, 38th, 45th, 48th, 49th, 69th, 79th, 81st, 86th, 91st terms are primes. - Shanzhen Gao, Sep 18 2013
Bourgain, Gamburd, and Sarnak have announced a proof that almost all Markoff numbers are composite--see A256395. Equivalently, the prime Markoff numbers A178444 have density zero among all Markoff numbers. (It is conjectured that infinitely many Markoff numbers are prime.) - Jonathan Sondow, Apr 30 2015
According to Sarnak on Apr 30 2015, all claims to have proved the unicity conjecture have turned out to be false. - Jonathan Sondow, May 01 2015
The numeric value of C = lim (number of Markoff numbers < x) / log^2(3x) given in Zagier's paper and quoted above suffers from an accidentally omitted digit and rounding errors. The correct value is C = 0.180717104711806... (see A261613 for more digits). - Christopher E. Thompson, Aug 22 2015
Named after the Russian mathematician Andrey Andreyevich Markov (1856-1922). - Amiram Eldar, Jun 10 2021

Martin Aigner, Markov's theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings. Springer, 2013. x+257 pp. ISBN: 978-3-319-00887-5; 978-3-319-00888-2 MR3098784
John H. Conway and Richard K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 187.
Jean-Marie De Koninck, Those Fascinating Numbers, Amer. Math. Soc., 2009, page 86.
Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.31.3, p. 200.
Richard K. Guy, Unsolved Problems in Number Theory, D12.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, notes on ch. 24.6 (p. 412)
Florian Luca and A. Srinivasan, Markov equation with Fibonacci components, Fib. Q., 56 (No. 2, 2018), 126-129.
Richard A. Mollin, Advanced Number Theory with Applications, Chapman & Hall/CRC, Boca Raton, 2010, 123-125.
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).

T. D. Noe, Table of n, a(n) for n = 1..1000
Ryuji Abe and Benoît Rittaud, On palindromes with three or four letters associated to the Markoff spectrum, Discrete Mathematics, Vol. 340, No. 12 (2017), pp. 3032-3043.
Tom Ace, Markoff numbers.
Enrico Bombieri, Continued fractions and the Markoff tree, Expo. Math., Vol. 25, No. 3 (2007), pp. 187-213.
Jean Bourgain, Alex Gamburd, and Peter Sarnak, Markoff triples and strong approximation, Comptes Rendus Mathematique, Vol. 354, No. 2 (2016), pp. 131-135; arXiv preprint, arXiv:1505.06411 [math.NT], 2015.
Roger Descombes, Problèmes d'approximation diophantienne, L'Enseignement Math. (2), Vol. 6 (1960), pp. 18-26.
Roger Descombes, Problèmes d'approximation diophantienne, L'Enseignement Math. (2), Vol. 6 (1960), pp. 18-26. [Annotated scanned copy]
Jonathan David Evans and Ivan Smith, Markov numbers and Lagrangian cell complexes in the complex projective plane, Geometry & Topology, Vol. 22 (2018), pp. 1143-1180; arXiv preprint, arXiv:1606.08656 [math.SG], 2016-2017.
Sam Evans, Perrine Jouteur, Sophie Morier-Genoud, and Valentin Ovsienko, On q-deformed Markov numbers. Cohn matrices and perfect matchings with weighted edges, hal-05186307 (2025). See p. 2.
Georg Frobenius, Über die Markoffschen Zahlen, Sitzungsberichte der Königlichen Preußischen Akademie der Wissenschaften, Jahrgang 1913.
Carlos A. Gómez, Jhonny C. Gómez, and Florian Luca, Markov triples with k-generalized Fibonacci components, Annales Mathematicae et Informaticae, Vol. 52 (2020), pp. 107-115.
Richard K. Guy, Don't try to solve these problems, Amer. Math. Monthly, Vol. 90, No. 1 (1983), pp. 35-41.
Yasuaki Gyoda, Positive integer solutions to (x+y)^2+(y+z)^2+(z+x)^2=12xyz, arXiv:2109.09639 [math.NT], 2021.
Hayder Raheem Hashim and Szabolcs Tengely, Solutions of a generalized markoff equation in Fibonacci numbers, Mathematica Slovaca, Vol. 70, No. 5 (2020), pp. 1069-1078.
Masanobu Kaneko, Congruences of Markoff numbers via Farey parametrization, Preliminary Report, Dec 2011, AMS 1078-11-124, listed in Abstracts of Papers Presented to AMS, Vol.33, No.2, Issue 168, Spring 2012.
Sebastien Labbé, Mélodie Lapointe, and Wolfgang Steiner, A q-analog of the Markoff injectivity conjecture holds, arXiv:2212.09852 [math.CO], 2022.
Clément Lagisquet, Edita Pelantová, Sébastien Tavenas, and Laurent Vuillon, On the Markov numbers: fixed numerator, denominator, and sum conjectures, arXiv:2010.10335 [math.CO], 2020.
Mong Lung Lang and Ser Peow Tan, A simple proof of the Markoff conjecture for prime powers, Geometriae Dedicata, Vol. 129 (2007), pp. 15-22; arXiv preprint, arXiv:math/0508443 [math.NT], 2005.
Kyungyong Lee, Li Li, Michelle Rabideau, and Ralf Schiffler, On the ordering of the Markov numbers, arXiv:2010.13010 [math.NT], 2020.
James Propp, The combinatorics of Markov numbers, U. Wisconsin Combinatorics Seminar, April 4, 2005.
S. G. Rayaguru, M. K. Sahukar, and G. K. Panda, Markov equation with components of some binary recurrent sequences, Notes on Number Theory and Discrete Mathematics, Vol. 26, No. 3 (2020), pp. 149-159.
Norbert Riedel, On the Markoff Equation, arXiv:1208.4032 [math.NT], 2012-2015.
Julieth F. Ruiz, Jose L. Herrera, and Jhon J. Bravo, Markov Triples with Generalized Pell Numbers, Mathematics 12, 108, (2024).
Anitha Srinivasan, Markoff numbers and ambiguous classes, Journal de théorie des nombres de Bordeaux, 21 no. 3 (2009), pp. 757-770.
Anitha Srinivasan, The Markoff-Fibonacci Numbers, Fibonacci Quart., Vol. 58, No. 5 (2020), pp. 222-228.
Michel Waldschmidt, Open Diophantine problems, arXiv:math/0312440 [math.NT], 2003-2004.
Eric Weisstein's World of Mathematics, Markov Number.
Wikipedia, Markov number.
Don Zagier, On the number of Markoff numbers below a given bound, Mathematics of Computation, Vol. 39, No. 160 (1982), pp. 709-723.
Ying Zhang, An Elementary Proof of Markoff Conjecture for Prime Powers, arXiv:math/0606283 [math.NT], 2006-2007.
Ying Zhang, Congruence and uniqueness of certain Markov numbers, Acta Arithmetica, Vol. 128 (2007), pp. 295-301.

Cf. A178444, A256395, A000045, A001653, A004280, A158381, A158384.

m = {1}; Do[x = m[[i]]; y = m[[j]]; a = (3*x*y + Sqrt[ -4*x^2 - 4*y^2 + 9*x^2*y^2])/2; b = (3*x*y + Sqrt[ -4*x^2 - 4*y^2 + 9*x^2*y^2])/2; If[ IntegerQ[a], m = Union[ Join[m, {a}]]]; If[ IntegerQ[b], m = Union[ Join[m, {b}]]], {n, 8}, {i, Length[m]}, {j, i}]; Take[m, 40] (* Robert G. Wilson v, Oct 05 2005 *)
terms = 40; depth0 = 10; Clear[ft]; ft[n_] := ft[n] = Module[{f}, f[] = {1, 2, 5}; f[ud___, u(*up*)] := f[ud, u] = Module[{g = f[ud]}, {g[[1]], g[[3]], 3*g[[1]]*g[[3]] - g[[2]]}]; f[ud___, d(*down*)] := f[ud, d] = Module[{g = f[ud]}, {g[[2]], g[[3]], 3*g[[2]]*g[[3]] - g[[1]]}]; f @@@ Tuples[{u, d}, n] // Flatten // Union // PadRight[#, terms]&]; ft[n = depth0]; ft[n++]; While[ft[n] != ft[n - 1], n++]; Print["depth = n = ", n]; A002559 = ft[n] (* Jean-François Alcover, Aug 29 2017 *)
MAX=10^10;
data=NestWhile[Select[Union[Sort/@Flatten[Table[{a, b, 3a b -c}/.MapThread[Rule, {{a, b, c}, #}]&/@Map[RotateLeft[ii, #]&, Range[3]], {ii, #}], 1]], Max[#]Xianwen Wang, Aug 22 2021 *)

markov = set[tuple[int, int, int]]
def MarkovNumbers(len: int = 50, MAX: int = 10**10) -> list[int]:
    cur: markov = {(1, 1, 1), (1, 1, 2), }
    def step(triples: markov) -> markov:
        ret: markov = set()
        for (a, b, c) in triples:
            for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
                t = (x, y, 3 * x * y - z)
                if max(t) < MAX: ret.add(t)
        return ret
    while True:
        new = step(cur)
        if new == cur: break
        cur = new
    return sorted({n for triple in cur for n in triple})[:len]
print(MarkovNumbers(len=42))  # Peter Luschny, Aug 10 2025

Name clarified by Wolfdieter Lang, Jan 22 2015

A083140 Sieve of Eratosthenes arranged as an array and read by antidiagonals in the up direction; n-th row has property that smallest prime factor is prime(n).

Original entry on oeis.org

2, 3, 4, 5, 9, 6, 7, 25, 15, 8, 11, 49, 35, 21, 10, 13, 121, 77, 55, 27, 12, 17, 169, 143, 91, 65, 33, 14, 19, 289, 221, 187, 119, 85, 39, 16, 23, 361, 323, 247, 209, 133, 95, 45, 18, 29, 529, 437, 391, 299, 253, 161, 115, 51, 20, 31, 841, 667, 551, 493, 377, 319, 203, 125, 57, 22

Offset: 2

Yasutoshi Kohmoto, Jun 05 2003

A permutation of natural numbers >= 2.
The proportion of integers in the n-th row of the array is given by A005867(n-1)/A002110(n) = A038110(n)/A038111(n). - Peter Kagey, Jun 03 2019, based on comments by Jamie Morken and discussion with Tom Hanlon.
The proportion of the integers after the n-th row of the array is given by A005867(n)/A002110(n). - Tom Hanlon, Jun 08 2019

			Array begins:
   2   4   6   8  10  12  14  16  18  20  22  24 .... (A005843 \ {0})
   3   9  15  21  27  33  39  45  51  57  63  69 .... (A016945)
   5  25  35  55  65  85  95 115 125 145 155 175 .... (A084967)
   7  49  77  91 119 133 161 203 217 259 287 301 .... (A084968)
  11 121 143 187 209 253 319 341 407 451 473 517 .... (A084969)
  13 169 221 247 299 377 403 481 533 559 611 689 .... (A084970)

Cf. A083141 (main diagonal), A083221 (transpose), A004280, A038179, A084967, A084968, A084969, A084970, A084971.
Arrays of integers grouped into rows by various criteria:
by greatest prime factor: A125624,
by lowest prime factor: this sequence (upward antidiagonals), A083221 (downward antidiagonals),
by number of distinct prime factors: A125666,
by number of prime factors counted with multiplicity: A078840,
by prime signature: A095904,
by ordered prime signature: A096153,
by number of divisors: A119586,
by number of 1's in binary expansion: A066884 (upward), A067576 (downward),
by distance to next prime: A192179.
Cf. A002110, A005867, A038110, A038111.

a = Join[ {Table[2n, {n, 1, 12}]}, Table[ Take[ Prime[n]*Select[ Range[100], GCD[ Prime[n] #, Product[ Prime[i], {i, 1, n - 1}]] == 1 &], 12], {n, 2, 12}]]; Flatten[ Table[ a[[i, n - i]], {n, 2, 12}, {i, n - 1, 1, -1}]]
(* second program: *)
rows = 12; Clear[T]; Do[For[m = p = Prime[n]; k = 1, k <= rows, m += p, If[ FactorInteger[m][[1, 1]] == p, T[n, k++] = m]], {n, rows}]; Table[T[n - k + 1, k], {n, rows}, {k, n}] // Flatten (* Jean-François Alcover, Mar 08 2016 *)

More terms from Hugo Pfoertner and Robert G. Wilson v, Jun 13 2003

A038179 Result of second stage of sieve of Eratosthenes (after eliminating multiples of 2 and 3).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151

Offset: 1

N. J. A. Sloane, Dec 11 1999

2, 3 and numbers of the form 6m +- 1.
Apart from first two terms, same as A007310.
Terms of this sequence (starting from the third term) are equal to the result of the expression sqrt(4!*(k+1) + 1) - but only when this expression yields integral values (that is when the parameter k takes values, which are terms of A144065). - Alexander R. Povolotsky, Sep 09 2008
For every integer n>2, n is in this sequence iff Product_{k=2..oo} 1/(1 - 1/k^n) = Product_{k=1..n} Gamma( 2 - (-1)^(k*(1 + 1/n)) ). - Federico Provvedi, Nov 07 2024

Fred S. Roberts, Applied Combinatorics, Prentice-Hall, 1984, p. 256.

G. C. Greubel, Table of n, a(n) for n = 1..2500
Ahmed Hamdy A. Diab, Sequence eliminating law (SEL) and the interval formulas of prime numbers, arXiv:2012.03052 [math.NT], 2020.
H. B. Meyer, Eratosthenes' sieve.
Index entries for sequences generated by sieves.

Cf. A004280, A007310, A144065.

max = 200; Complement[Range[2, max], 2Range[2, Ceiling[max/2]], 6Range[2, Ceiling[max/6]] + 3] (* Alonso del Arte, May 16 2014 *)
Prepend[Table[3*n - Mod[ Mod[n, 2] + 1, n], {n, 1, 999}], 2] (* Mikk Heidemaa, Nov 02 2017 *)

O.g.f.: x*(2 + x + x^3 + 2x^4)/((1+x)*(1-x)^2). - R. J. Mathar, May 23 2008
a(n) = (1/9)*(4*n^3 + 3*n^2 + 1 - Kronecker(-3,n+1)). - Ralf Stephan, Jun 01 2014
From Mikk Heidemaa, Oct 28 2017: (Start)
a(n) = floor((41/21 - (3 mod n))^(-3*n+5)) + 3*n - 4 (n > 0).
a(n+1) = 3*n - ((n mod 2)+1) mod n (n > 0). (End)
a(n+2) = 2*floor((3*n+1)/2) + 1 for n>=1; see (17) in Diab link. - Michel Marcus, Dec 14 2020
Sum_{n>=1} (-1)^(n+1)/a(n) = (7-sqrt(3)*Pi)/6. - Amiram Eldar, Sep 22 2022

Name edited by Michel Marcus, Dec 14 2020

A055399 Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 4, 1, 4, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5, 1, 5, 1, 2, 1, 3, 1, 5, 1, 2, 1, 5, 1, 5, 1, 2, 1, 4, 1, 5, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5

Offset: 3

Henry Bottomley, May 15 2000

Primes are known as primes actually one step before a(n): at step k of the sieve, multiples of prime(k) are removed, the smallest integer removed being prime(k)^2; every remaining integer less than prime(k+1)^2 will then never be removed, and it is newly known at step k for those between prime(k)^2 and prime(k+1)^2. For example, at step 3, multiples of prime(3) = 5 are removed and remaining integers after this step are prime up to prime(4)^2 = 49; then, 29, 31, 37, 41, 43, 47 are known as prime at step 3. - Jean-Christophe Hervé, Nov 01 2013

			a(7)=2 because 7 is not removed by the first two stages of the sieve, but is less than the square of the second prime (though not the square of the first); a(35)=3 because 35 is removed in the third stage as a multiple of 5.

T. D. Noe, Table of n, a(n) for n = 3..10000
H. B. Meyer, Eratosthenes' sieve
J. Britton, Sieve of Eratosthenes Applet
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes

Cf. A000040, A002808, A004280, A038179, A055396, A054403, A055398, A083269, A010051, A056811.

a[n_ /; !PrimeQ[n]] := PrimePi[ FactorInteger[n][[1, 1]]]; a[n_ /; PrimeQ[n]] := PrimePi[ NextPrime[ Sqrt[n]]]; Table[a[n], {n, 3, 107}](* Jean-François Alcover, Jun 11 2012, after formula *)

If n is composite, a(n) = A055396(n); if n is prime, a(n) = A056811(n)+1. [Corrected by Charles R Greathouse IV, Sep 03 2013]

a(n) = A010051(n)*(A056811(n)+1)+(1-A010051(n))*A055396(n). - Jean-Christophe Hervé, Nov 01 2013

A316430 Heinz numbers of integer partitions whose length is equal to the GCD of all the parts.

Original entry on oeis.org

1, 2, 9, 21, 39, 57, 87, 91, 111, 125, 129, 159, 183, 203, 213, 237, 247, 267, 301, 303, 321, 325, 339, 377, 393, 417, 427, 453, 489, 519, 543, 551, 553, 559, 575, 579, 597, 669, 687, 689, 707, 717, 753, 789, 791, 813, 817, 843, 845, 879, 923, 925, 933, 951, 973

Offset: 1

Gus Wiseman, Jul 02 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

2 is the only even term in the sequence. 3k is in the sequence if and only if k is in A031215. 5k is in the sequence if and only if k = pq with p and q in A031336.

			Sequence of integer partitions whose length is equal to their GCD begins: (), (1), (2,2), (4,2), (6,2), (8,2), (10,2), (6,4), (12,2), (3,3,3), (14,2), (16,2), (18,2), (10,4), (20,2), (22,2), (8,6), (24,2), (14,4), (26,2), (28,2), (6,3,3).

Subsequence of A004280.

Cf. A056239, A067538, A074761, A143773, A289508, A289509, A296150, A316413, A316431, A316432, A316433, A031215, A031336.

Select[Range[200],PrimeOmega[#]==GCD@@Cases[FactorInteger[#],{p_,k_}:>PrimePi[p]]&]

is(n,f=factor(n))=gcd(apply(primepi,f[,1]))==vecsum(f[,2]) \\ Charles R Greathouse IV, Jul 25 2024

a(n) << n log^2 n, can this be improved? - Charles R Greathouse IV, Jul 25 2024

A174296 Row sums of A174294.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2

Offset: 0

Mats Granvik, Mar 15 2010

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,1).

Cf. A010693, A112468, A112467, A174294, A174295, A174297.

[n lt 2 select (n+1) else 2 + (n mod 2): n in [0..110]]; // G. C. Greubel, Nov 25 2021

Table[If[n<2, n+1, (5-(-1)^n)/2], {n,0,110}] (* G. C. Greubel, Nov 25 2021 *)

[1,2]+[(5-(-1)^n)/2 for n in (2..110)] # G. C. Greubel, Nov 25 2021

a(A004280(n)) = 3 for n > 2.
From G. C. Greubel, Nov 25 2021: (Start)
a(n) = a(n-2) for n > 3, with a(0) = 1, a(1) = 2, a(2) = 2, a(3) = 3.
a(n) = (5 - (-1)^n)/2 for n > 1, with a(0) = 1, a(1) = 2.
a(n) = (n+1)*[n<2] + A010693(n)*[n>1].
G.f.: (1_+ 2*x + x^2 + x^3)/(1 - x^2).
E.g.f.: (1/2)*( -exp(-x) - 2*(1+x) + 5*exp(x) ). (End)

cp's OEIS Frontend

A368382 a(1) = 1; for n > 1, a(n) is the least positive integer not already in the sequence such that a(n) == a(n-1) (mod A004280(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

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

A002858 Ulam numbers: a(1) = 1; a(2) = 2; for n>2, a(n) = least number > a(n-1) which is a unique sum of two distinct earlier terms.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Julia

Maple

Mathematica

PARI

Python

Extensions

A083221 Sieve of Eratosthenes arranged as an array and read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A002559 Markoff (or Markov) numbers: union of positive integers x, y, z satisfying x^2 + y^2 + z^2 = 3*x*y*z.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A083140 Sieve of Eratosthenes arranged as an array and read by antidiagonals in the up direction; n-th row has property that smallest prime factor is prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A038179 Result of second stage of sieve of Eratosthenes (after eliminating multiples of 2 and 3).

Views

Author

Keywords

A002559 Markoff (or Markov) numbers: union of positive integers x, y, z satisfying x^2 + y^2 + z^2 = 3xy*z.