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.

%I A006255 M4064 #95 Apr 29 2025 04:45:03
%S A006255 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 A006255 25,39,35,40,58,42,62,45,44,51,48,36,74,57,52,50,82,56,86,55,60,69,94,
%U A006255 54,49,63,68,65,106,70,66,72,76,87,118,75,122,93,77,64,78,80,134,85,92,84
%N 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.
%C A006255 Every nonprime appears exactly once in this sequence.
%C A006255 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 A006255 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 A006255 From _David A. Corneth_, Oct 26 2016: (Start)
%C A006255 Is for all k*p in A277624, a(k*p) = (k+1) * p?
%C A006255 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 A006255 (End)
%C A006255 a(n) <= A072905(n).
%C A006255 a(n) <= 2*n for all n > 3.
%C A006255 a(n) >= n + A006530(A007913(n)) for all nonsquare n. - _Peter Kagey_, Feb 21 2015
%D A006255 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 A006255 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006255 Peter Kagey, <a href="/A006255/b006255.txt">Table of n, a(n) for n = 1..10000</a>
%H A006255 Sarosh Adenwalla, <a href="https://arxiv.org/abs/2504.19196">On a Generalisation of a Function of Ron Graham's</a>, arXiv:2504.19196 [math.NT], 2025.
%H A006255 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 A006255 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 A006255 If n is a square we can take t=1 and a(n)=n.
%F A006255 a(n) = A245499(n,A066400(n)). - _Reinhard Zumkeller_, Jul 25 2014
%F A006255 a(n) = A092487(n) + n. - _Peter Kagey_, Oct 22 2016
%e A006255 a(2) = 6 because the best such sequence is 2,3,6.
%e A006255 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 A006255 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 A006255 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 A006255 If squares are omitted we get A233421.
%Y A006255 A067565 is the inverse of R. L. Graham's sequence.
%Y A006255 Cf. A245499, A070229, A072905, A092487.
%K A006255 nonn,nice
%O A006255 1,2
%A A006255 _N. J. A. Sloane_ and _Robert G. Wilson v_
%E A006255 More terms from _Robert G. Wilson v_, Jan 30 2002
%E A006255 Erroneous program (pointed out by _Peter Kagey_) removed by _Reinhard Zumkeller_, Nov 28 2014