The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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) 29
 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 (list; graph; refs; listen; history; text; internal format)
 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] 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: A200133 A021150 A065166 * A110760 A050710 A123092 Adjacent sequences:  A006252 A006253 A006254 * A006256 A006257 A006258 KEYWORD nonn,nice AUTHOR 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 6 22:30 EDT 2020. Contains 335484 sequences. (Running on oeis4.)