A066401 -id:A066401 - cp's OEIS frontend

A006255 R. L. Graham's sequence: a(n) = smallest m for which there is a sequence n = b_1 < b_2 < ... < b_t = m such that b_1b_2...*b_t is a perfect square.

1, 6, 8, 4, 10, 12, 14, 15, 9, 18, 22, 20, 26, 21, 24, 16, 34, 27, 38, 30, 28, 33, 46, 32, 25, 39, 35, 40, 58, 42, 62, 45, 44, 51, 48, 36, 74, 57, 52, 50, 82, 56, 86, 55, 60, 69, 94, 54, 49, 63, 68, 65, 106, 70, 66, 72, 76, 87, 118, 75, 122, 93, 77, 64, 78, 80, 134, 85, 92, 84

Offset: 1

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

Every nonprime appears exactly once in this sequence.
If n is a square we can take t=1 and a(n) = n. If n is a prime > 3, then a(n) = 2n and t=3. If n is twice a prime, say p, then a(n) = 3p most of the time. The sequence b_1 < b_2 < ... < b_t will not contain either perfect squares or primes for they bring nothing to the solution. Also I know of no n such that t = 2. - Robert G. Wilson v, Jan 30 2002
Let k be a fixed integer and p be a prime, then a(k*p) = (k+1)*p for sufficiently large p. - Peter Kagey, Feb 03 2015
From David A. Corneth, Oct 26 2016: (Start)
Is for all k*p in A277624, a(k*p) = (k+1) * p?
Conjecture: Let b(n) = A006530(A007913(n)). If b(n)^2 >= 2 * n then a(n) = n + b(n) except for n = 3, 10, and 171.
(End)
a(n) <= A072905(n).
a(n) <= 2*n for all n > 3.
a(n) >= n + A006530(A007913(n)) for all nonsquare n. - Peter Kagey, Feb 21 2015

			a(2) = 6 because the best such sequence is 2,3,6.
For n = 3 through 6 the {smallest m then smallest t then smallest product} solutions are 3,6,8; 4; 5,8,10; 6,8,12.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., Problem 4.39, pages 147, 616, 533. [Reference revised by N. J. A. Sloane, Jan 13 2014]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Peter Kagey, Table of n, a(n) for n = 1..10000
Sarosh Adenwalla, On a Generalisation of a Function of Ron Graham's, arXiv:2504.19196 [math.NT], 2025.
R. L. Graham, Bijection between integers and composites, Problem 1242, Math. Mag., 60 (1987), p. 180. [Note that unless you subscribe to JSTOR this link will only show page 178, which contains a different problem proposed by R. L. Graham. - _N. J. A. Sloane_, Jan 13 2014]
Peter Kagey and Krishna Rajesh, On a Conjecture about Ron Graham's Sequence, arXiv:2410.04728 [math.NT], 2024.

Having minimized m, next minimize t, then minimize product: A066400 and A066401 give values of t and square root of b_1*...*b_t.
If squares are omitted we get A233421.
A067565 is the inverse of R. L. Graham's sequence.
Cf. A245499, A070229, A072905, A092487.

Table[k = 0; Which[IntegerQ@ Sqrt@ n, k, And[PrimeQ@ n, n > 3], k = n, True, While[Length@ Select[n Map[Times @@ # &, n + Rest@ Subsets@ Range@ k], IntegerQ@ Sqrt@ # &] == 0, k++]]; k + n, {n, 40}] (* Michael De Vlieger, Oct 26 2016 *)

If n is a square we can take t=1 and a(n)=n.
a(n) = A245499(n,A066400(n)). - Reinhard Zumkeller, Jul 25 2014
a(n) = A092487(n) + n. - Peter Kagey, Oct 22 2016

More terms from Robert G. Wilson v, Jan 30 2002

Erroneous program (pointed out by Peter Kagey) removed by Reinhard Zumkeller, Nov 28 2014

A066400 Smallest values of t arising in R. L. Graham's sequence (A006255).

Original entry on oeis.org

1, 3, 3, 1, 3, 3, 3, 4, 1, 4, 3, 3, 3, 5, 4, 1, 3, 3, 3, 3, 3, 3, 3, 3, 1, 4, 5, 4, 3, 3, 3, 3, 5, 4, 4, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 5, 6, 3, 4, 5, 3, 3, 4, 3, 5, 3, 4, 5, 1, 6, 5, 3, 3, 3, 5, 3, 5, 3, 3, 6, 3, 4, 5, 3, 3, 1, 3, 3, 4, 5, 3, 3, 3, 3, 6, 6, 5, 3, 3, 5, 3, 3, 6, 7, 1, 3, 6, 3, 5, 4

Offset: 1

N. J. A. Sloane, Dec 25 2001

nonn

Length of n-th row in table A245499. - Reinhard Zumkeller, Jul 25 2014
Indices of records are 1, 2, 8, 14, 52, 99, 589, 594, 595... (A277649) - Peter Kagey, Oct 24 2016
It is conjectured that 2 never appears in this sequence. a(n) = 2 if and only if A006255(n) = A072905(n). - Peter Kagey, Oct 25 2016
a(n) is three most of the time, then 5, then 6, then 4 for the first 1000 and the first 10000 terms. At n = 72, 78 and 85, a(n) is 4 or 5 and 4 and 5 occurred equally often so far. At 299, 301, 312, 322 and 403, a(n) is 4 or 6 and 4 and 6 occurred equally often so far. This doesn't happen for the first 10000 terms for 5 and 6. - David A. Corneth, Oct 25 2016

			a(2) = 3 because the best such sequence is 2,3,6 which has three terms.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 147.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1000 terms from Reinhard Zumkeller and Peter Kagey)
R. L. Graham, Bijection between integers and composites, Problem 1242, Math. Mag., 60 (1987), p. 180.

Cf. A006255, A066401, A072905.

Cf. A245499, A277649.

a066400 = length . a245499_row  -- Reinhard Zumkeller, Jul 25 2014

More terms from John W. Layman, Jul 14 2003

More terms from Joshua Zucker, May 18 2006

A245499 Table read by rows: n-th row contains the factors which occur when constructing R. L. Graham's sequence A006255, such that the number of factors and also the product is minimal.

Original entry on oeis.org

1, 2, 3, 6, 3, 6, 8, 4, 5, 8, 10, 6, 8, 12, 7, 8, 14, 8, 10, 12, 15, 9, 10, 12, 15, 18, 11, 18, 22, 12, 15, 20, 13, 18, 26, 14, 15, 18, 20, 21, 15, 18, 20, 24, 16, 17, 18, 34, 18, 24, 27, 19, 32, 38, 20, 24, 30, 21, 27, 28, 22, 24, 33, 23, 32, 46, 24, 27, 32

Offset: 1

Reinhard Zumkeller, Jul 25 2014

A066400(n) = length of n-th row.
A006255(n) = T(n,A066400(n)), last term in n-th row.
A245530(n) = A066401(n)^2 = product of n-th row.
For n > 2: A245508(n) = T(A000040(n),2).
T(n,k) denote b_k in the definition given in A006255.
From David A. Corneth, Oct 22 2016 and Oct 25 2016: (Start)
Frequency of n in this sequence: 1, 1, 2, 1, 1, 3, 1, 5, 1, 3, 1, 4, 1, 2, ... See A277606.
Primes and squares occur once in this sequence except for 3 which occurs twice.
In the first 10000 rows, 9522 occurs most often and appears 60 times. 6498 is a close second with 59 occurrences.
(End)

			.    n |  Row(n)                | A066400(n) | A245530(n) | A066401(n)
. -----+------------------------+------------+------------+-----------
.    1 |  [1]                   |          1 |          1 |          1
.    2 |  [2, 3, 6]             |          3 |         36 |          6
.    3 |  [3, 6, 8]             |          3 |        144 |         12
.    4 |  [4]                   |          1 |          4 |          2
.    5 |  [5, 8, 10]            |          3 |        400 |         20
.    6 |  [6, 8, 12]            |          3 |        576 |         24
.    7 |  [7, 8, 14]            |          3 |        784 |         28
.    8 |  [8, 10, 12, 15]       |          4 |      14400 |        120
.    9 |  [9]                   |          1 |          9 |          3
.   10 |  [10, 12, 15, 18]      |          4 |      32400 |        180
.   11 |  [11, 18, 22]          |          3 |       4356 |         66
.   12 |  [12, 15, 20]          |          3 |       3600 |         60
.   13 |  [13, 18, 26]          |          3 |       6084 |         78
.   14 |  [14, 15, 18, 20, 21]  |          5 |    1587600 |       1260
.   15 |  [15, 18, 20, 24]      |          4 |     129600 |        360
.   16 |  [16]                  |          1 |         16 |          4
.   17 |  [17, 18, 34]          |          3 |      10404 |        102
.   18 |  [18, 24, 27]          |          3 |      11664 |        108
.   19 |  [19, 32, 38]          |          3 |      23104 |        152
.   20 |  [20, 24, 30]          |          3 |      14400 |        120
.   21 |  [21, 27, 28]          |          3 |      15876 |        126
.   22 |  [22, 24, 33]          |          3 |      17424 |        132
.   23 |  [23, 32, 46]          |          3 |      33856 |        184
.   24 |  [24, 27, 32]          |          3 |      20736 |        144
.   25 |  [25]                  |          1 |         25 |          5 .

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., Problem 4.39, pages 147, 616, 533.

Peter Kagey, Table of n, a(n) for n = 1..44055 (Derived from David A. Corneth's unflattened file)
David A. Corneth, First 10000 rows unflattened

Cf. A006255, A006530, A007913, A010051, A010052, A020639, A049084, A066400 (row lengths), A066401, A089229, A151800, A245508, A245530 (row products), A277606.

Table[k = 0; While[Length@ # == 0 &@ Set[f, Select[Rest@ Subsets@ Range@ k, IntegerQ@ Sqrt[n (Times @@ # &[n + #])] &]], k++]; If[IntegerQ@ Sqrt@ n, k = {n}, k = n + Prepend[First@ f, 0]]; k, {n, 22}] (* Michael De Vlieger, Oct 26 2016 *)

Following a suggestion of Peter Kagey, definition clarified by Reinhard Zumkeller, Nov 28 2014. Also removed erroneous program and b-file.

A245530 a(n) = smallest square which is the product of a minimal set of distinct numbers not less than n.

Original entry on oeis.org

1, 36, 144, 4, 400, 576, 784, 14400, 9, 32400, 4356, 3600, 6084, 1587600, 129600, 16, 10404, 11664, 23104, 14400, 15876, 17424, 33856, 20736, 25, 876096, 25401600, 1254400, 53824, 44100, 61504, 57600, 85377600, 4161600, 2822400, 36, 136900, 116964, 97344

Offset: 1

Reinhard Zumkeller, Jul 25 2014

nonn

a(n) mod n = 0; a(n) mod A006255(n) = 0.

Peter Kagey, Table of n, a(n) for n = 1..1000 (First 125 terms from Reinhard Zumkeller)

Cf. A006255, A066400, A066401, A245499.

Haskell
```
a245530 = product . a245499_row
```

Table[k = 0; While[Length@ # == 0 &@ Set[f, Select[Rest@ Subsets@ Range@ k, IntegerQ@ Sqrt[n (Times @@ # &[n + #])] &]], k++]; If[IntegerQ@ Sqrt@ n, k = {n}, k = n + Prepend[First@ f, 0]]; Times @@ k, {n, 22}] (* Michael De Vlieger, Oct 26 2016 *)

a(n) = Product_{k=1..A066400(n)} A245499(n,k), product of n-th row in A245499.

a(n) = A066401(n)^2.

cp's OEIS Frontend

A006255 R. L. Graham's sequence: a(n) = smallest m for which there is a sequence n = b_1 < b_2 < ... < b_t = m such that b_1*b_2*...*b_t is a perfect square.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A066400 Smallest values of t arising in R. L. Graham's sequence (A006255).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Extensions

A245499 Table read by rows: n-th row contains the factors which occur when constructing R. L. Graham's sequence A006255, such that the number of factors and also the product is minimal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A245530 a(n) = smallest square which is the product of a minimal set of distinct numbers not less than n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A006255 R. L. Graham's sequence: a(n) = smallest m for which there is a sequence n = b_1 < b_2 < ... < b_t = m such that b_1b_2...*b_t is a perfect square.