%I M4064 #90 Oct 08 2024 06:26:30

%S 1,6,8,4,10,12,14,15,9,18,22,20,26,21,24,16,34,27,38,30,28,33,46,32,

%T 25,39,35,40,58,42,62,45,44,51,48,36,74,57,52,50,82,56,86,55,60,69,94,

%U 54,49,63,68,65,106,70,66,72,76,87,118,75,122,93,77,64,78,80,134,85,92,84

%N 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.

%C Every nonprime appears exactly once in this sequence.

%C 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

%C 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

%C From _David A. Corneth_, Oct 26 2016: (Start)

%C Is for all k*p in A277624, a(k*p) = (k+1) * p?

%C 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.

%C (End)

%C a(n) <= A072905(n).

%C a(n) <= 2*n for all n > 3.

%C a(n) >= n + A006530(A007913(n)) for all nonsquare n. - _Peter Kagey_, Feb 21 2015

%D 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]

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Peter Kagey, <a href="/A006255/b006255.txt">Table of n, a(n) for n = 1..10000</a>

%H R. L. Graham, <a href="http://www.jstor.org/stable/2689569">Bijection between integers and composites</a>, 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]

%H Peter Kagey and Krishna Rajesh, <a href="https://arxiv.org/abs/2410.04728">On a Conjecture about Ron Graham's Sequence</a>, arXiv:2410.04728 [math.NT], 2024.

%F If n is a square we can take t=1 and a(n)=n.

%F a(n) = A245499(n,A066400(n)). - _Reinhard Zumkeller_, Jul 25 2014

%F a(n) = A092487(n) + n. - _Peter Kagey_, Oct 22 2016

%e a(2) = 6 because the best such sequence is 2,3,6.

%e 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.

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

%Y Having minimized m, next minimize t, then minimize product: A066400 and A066401 give values of t and square root of b_1*...*b_t.

%Y If squares are omitted we get A233421.

%Y A067565 is the inverse of R. L. Graham's sequence.

%Y Cf. A245499, A070229, A072905, A092487.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_, _Robert G. Wilson v_

%E More terms from _Robert G. Wilson v_, Jan 30 2002

%E Erroneous program (pointed out by _Peter Kagey_) removed by _Reinhard Zumkeller_, Nov 28 2014