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.

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

Author

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

Keywords

• nonn
• nice

Comments

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

Examples

			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.
		

References

• 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).

Links

• 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.

Crossrefs

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.

Programs

Mathematica

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 *)

Formula

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

Extensions

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

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