|
|
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)
|
|
31
|
|
|
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
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) <= 2*n for all n > 3.
|
|
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
|
|
|
FORMULA
|
If n is a square we can take t=1 and a(n)=n.
|
|
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.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|