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. (Formerly M4064)

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,2

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

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

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.

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

Example

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.

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

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.

Sequence in context: A021150 A347407 A065166 * A110760 A050710 A123092

Adjacent sequences: A006252 A006253 A006254 * A006256 A006257 A006258

Keyword

nonn,nice

Author

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

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

Status

approved