A072905 -id:A072905 - cp's OEIS frontend

A255167 a(n) = A072905(n) - A006255(n).

3, 2, 4, 5, 10, 12, 14, 3, 7, 22, 22, 7, 26, 35, 36, 9, 34, 5, 38, 15, 56, 55, 46, 22, 11, 65, 13, 23, 58, 78, 62, 5, 88, 85, 92, 13, 74, 95, 104, 40, 82, 112, 86, 44, 20, 115, 94, 21, 15, 9, 136, 52, 106, 26, 154, 54, 152, 145, 118, 60, 122, 155, 35, 17

Offset: 1

Peter Kagey, Feb 15 2015

nonn

a(n) is strictly nonnegative because A072905 is an upper bound on A006255.
A066400(n) = 2 if and only if a(n) = 0.
a(n) > 0 for all n <= 10000.

Peter Kagey, Table of n, a(n) for n = 1..10000

Cf. A072905, A006255, A066400.

a(n) = A072905(n) - A006255(n).

A305677 Number of subsets of {n+1, n+2, ..., A072905(n)-1} whose product has the same squarefree part as n.

Original entry on oeis.org

1, 2, 8, 1, 64, 256, 2048, 4, 1, 131072, 262144, 32, 8388608, 33554432, 134217728, 1, 2147483648, 8, 34359738368, 1024, 549755813888, 4398046511104, 17592186044416, 8192, 2, 1125899906842624, 32, 65536, 72057594037927936, 576460752303423488

Offset: 1

Peter Kagey, Jun 08 2018

nonn

Conjecture: a(n) > 0.
If the conjecture is true, all terms are powers of two, and a(n) >= A259527(n).
a(n) = 0 if and only if A066400(n) = 2.
a(n) = 0 if and only if A255167(n) = 0.
a(n) <= 2^(A067722(n) - 1). - Peter Kagey, Nov 13 2018

			For n = 3, the a(3) = 8 subsets of {4, 5, ..., 11} with a product with squarefree part of 3 are {4, 5, 6, 9, 10}, {4, 5, 6, 10}, {4, 6, 8}, {4, 6, 8, 9}, {5, 6, 9, 10}, {5, 6, 10}, {6, 8}, and {6, 8, 9}.

Peter Kagey, Table of n, a(n) for n = 1..200

Cf. A005117, A006255, A066400, A072905, A255167.

A086481 Erroneous version of A072905.

Original entry on oeis.org

4, 8, 12, 9, 125, 24, 343, 18, 16, 40, 1331, 48, 2197, 56, 3375

Offset: 0

dead

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_1b_2...*b_t is a perfect square.

Original entry on oeis.org

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

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

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

			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.

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

Peter Kagey, Table of n, a(n) for n = 1..10000
Sarosh Adenwalla, On a Generalisation of a Function of Ron Graham's, arXiv:2504.19196 [math.NT], 2025.
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.

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.

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

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

More terms from Robert G. Wilson v, Jan 30 2002

Erroneous program (pointed out by Peter Kagey) removed by Reinhard Zumkeller, Nov 28 2014

A066400 Smallest values of t arising in R. L. Graham's sequence (A006255).

Original entry on oeis.org

1, 3, 3, 1, 3, 3, 3, 4, 1, 4, 3, 3, 3, 5, 4, 1, 3, 3, 3, 3, 3, 3, 3, 3, 1, 4, 5, 4, 3, 3, 3, 3, 5, 4, 4, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 3, 5, 6, 3, 4, 5, 3, 3, 4, 3, 5, 3, 4, 5, 1, 6, 5, 3, 3, 3, 5, 3, 5, 3, 3, 6, 3, 4, 5, 3, 3, 1, 3, 3, 4, 5, 3, 3, 3, 3, 6, 6, 5, 3, 3, 5, 3, 3, 6, 7, 1, 3, 6, 3, 5, 4

Offset: 1

N. J. A. Sloane, Dec 25 2001

nonn

Length of n-th row in table A245499. - Reinhard Zumkeller, Jul 25 2014
Indices of records are 1, 2, 8, 14, 52, 99, 589, 594, 595... (A277649) - Peter Kagey, Oct 24 2016
It is conjectured that 2 never appears in this sequence. a(n) = 2 if and only if A006255(n) = A072905(n). - Peter Kagey, Oct 25 2016
a(n) is three most of the time, then 5, then 6, then 4 for the first 1000 and the first 10000 terms. At n = 72, 78 and 85, a(n) is 4 or 5 and 4 and 5 occurred equally often so far. At 299, 301, 312, 322 and 403, a(n) is 4 or 6 and 4 and 6 occurred equally often so far. This doesn't happen for the first 10000 terms for 5 and 6. - David A. Corneth, Oct 25 2016

			a(2) = 3 because the best such sequence is 2,3,6 which has three terms.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 147.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1000 terms from Reinhard Zumkeller and Peter Kagey)
R. L. Graham, Bijection between integers and composites, Problem 1242, Math. Mag., 60 (1987), p. 180.

Cf. A006255, A066401, A072905.

Cf. A245499, A277649.

a066400 = length . a245499_row  -- Reinhard Zumkeller, Jul 25 2014

More terms from John W. Layman, Jul 14 2003

More terms from Joshua Zucker, May 18 2006

A254732 a(n) is the least k > n such that n divides k^2.

Original entry on oeis.org

2, 4, 6, 6, 10, 12, 14, 12, 12, 20, 22, 18, 26, 28, 30, 20, 34, 24, 38, 30, 42, 44, 46, 36, 30, 52, 36, 42, 58, 60, 62, 40, 66, 68, 70, 42, 74, 76, 78, 60, 82, 84, 86, 66, 60, 92, 94, 60, 56, 60, 102, 78, 106, 72, 110, 84, 114, 116, 118, 90, 122, 124, 84, 72

Offset: 1

Peter Kagey, Feb 06 2015

A073353(n) <= a(n) <= 2*n. Any prime that divides n must also divide a(n), and because n divides (2*n)^2.

Are all terms even? -Harvey P. Dale, Aug 07 2025

			a(12) = 18 because 12 divides 18^2, but 12 does not divide 13^2, 14^2, 15^2, 16^2, or 17^2.

Peter Kagey, Table of n, a(n) for n = 1..5000

Cf. A254733 (similar, with k^3), A254734 (similar, with k^4), A073353 (similar, with limit m->infinity of k^m).

Cf. A253905.

a254732 n = head [k | k <- [n + 1 ..], mod (k ^ 2) n == 0]
-- Reinhard Zumkeller, Feb 07 2015

lk[n_]:=Module[{k=n+1},While[!Divisible[k^2,n],k++];k]; Array[lk,70] (* Harvey P. Dale, Nov 05 2017 *)
Table[Module[{k=n+1},While[PowerMod[k,2,n]!=0,k++];k],{n,70}] (* Harvey P. Dale, Aug 07 2025 *)

a(n)=for(k=n+1,2*n,if(k^2%n==0,return(k)))
vector(100,n,a(n)) \\ Derek Orr, Feb 06 2015

a(n)=my(t=factorback(factor(n)[,1])); forstep(k=n+t,2*n,t,if(k^2%n==0, return(k))) \\ Charles R Greathouse IV, Feb 07 2015

def A254732(n):
    k = n + 1
    while pow(k,2,n):
        k += 1
    return k # Chai Wah Wu, Feb 15 2015

def a(n)
  (n+1..2*n).find { |k| k**2 % n == 0 }
end

a(n) = sqrt(n*A072905(n)).
a(n) = A019554(n)*(A000188(n)+1).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 + zeta(3)/zeta(2) = 1 + A253905 = 1.73076296940143849872... . - Amiram Eldar, Feb 17 2024

A254767 a(n) is the least k > n such that k*n is a cube.

Original entry on oeis.org

8, 4, 9, 16, 25, 36, 49, 27, 24, 100, 121, 18, 169, 196, 225, 32, 289, 96, 361, 50, 441, 484, 529, 72, 40, 676, 64, 98, 841, 900, 961, 54, 1089, 1156, 1225, 48, 1369, 1444, 1521, 200, 1681, 1764, 1849, 242, 75, 2116, 2209, 288, 56, 160, 2601, 338, 2809, 108

Offset: 1

Peter Kagey, Feb 07 2015

a(n) <= n^2 for all n > 1 because n * n^2 = n^3.

			a(12) = 18 because 12*18 = 6^3 (and 12*13, 12*14, 12*15, 12*16, 12*17 are not perfect cubes).

Peter Kagey, Table of n, a(n) for n = 1..5000

Cf. A072905 (an analogous sequence for squares).

Cf. A048798 (similar sequence, no restriction that a(n) > n).

f[n_] := Block[{k = n + 1}, While[! IntegerQ@ Power[k n, 1/3], k++]; k]; Array[f, 54] (* Michael De Vlieger, Mar 17 2015 *)

a(n)=if (n==1, 8, for(k=n+1, n^2, if(ispower(k*n, 3), return(k))))
vector(100, n, a(n)) \\ Derek Orr, Feb 07 2015

a(n) = {f = factor(n); for (i=1, #f~, if (f[i,2] % 3, f[i,2] = 3 - f[i,2]);); cb = factorback(f); cbr = sqrtnint(cb*n, 3); cb = cbr^3; k = cb/n; while((type(k=cb/n) != "t_INT") || (k<=n), cbr++; cb = cbr^3;); k;} \\ Michel Marcus, Mar 14 2015

def a(n)
  min = (n**(2/3.0)).ceil
  (min..n+1).each { |i| return i**3/n if i**3 % n == 0 && i**3 > n**2 }
end

A277781 a(n) is the least k > n such that nk or nk^2 is a cube.

Original entry on oeis.org

8, 4, 9, 16, 25, 36, 49, 27, 24, 80, 88, 18, 104, 112, 120, 32, 136, 96, 152, 50, 168, 176, 184, 72, 40, 208, 64, 98, 232, 240, 248, 54, 264, 272, 280, 48, 296, 304, 312, 135, 328, 336, 344, 242, 75, 368, 376, 162, 56, 160, 408, 338, 424, 108, 440, 189, 456

Offset: 1

Peter Kagey, Oct 30 2016

a(n) is 1-to-1.

			a(2)  = 4  because 2  * 4    =  2^3;
a(10) = 80 because 10 * 80^2 = 40^3.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A072905, A254767, A277780.

Table[SelectFirst[n + Range[7 + n^2], AnyTrue[Power[#, 1/3] & /@ {n #, n #^2}, IntegerQ] &], {n, 57}] (* Michael De Vlieger, Feb 03 2018 *)

a(n)=my(f=factor(n),tf=f,a,b); tf[,2]%=3; b=factorback(tf); tf[,2]=2*f[,2]%3; a=factorback(tf); min((sqrtnint(n\a,3)+1)^3*a, (sqrtnint(n\b,3)+1)^3*b) \\ Charles R Greathouse IV, Oct 31 2016

a(n) = min(A254767(n), A277780(n)).

A277780 a(n) is the least k > n such that n*k^2 is a cube.

Original entry on oeis.org

8, 16, 24, 32, 40, 48, 56, 27, 72, 80, 88, 96, 104, 112, 120, 54, 136, 144, 152, 160, 168, 176, 184, 81, 200, 208, 64, 224, 232, 240, 248, 108, 264, 272, 280, 288, 296, 304, 312, 135, 328, 336, 344, 352, 360, 368, 376, 162, 392, 400, 408, 416, 424, 128, 440

Offset: 1

Peter Kagey, Oct 30 2016

a(n) is bounded above by 8*n (A008590) because n*(8*n)^2 = (4*n)^3.
If and only if n is cubefree, a(n) = 8n. - David A. Corneth, Nov 01 2016
Theorem: If n = q*m^3 with q cubefree then k = q*(m+1)^3. - Hartmut F. W. Hoft, Nov 02 2016
Proof: let q have u distinct prime divisors p_i. Then q = Product_{i=1..u}(p_i^e_i) where e_i > 0 since p_i|q and e_i < 3 since q is cubefree. Therefore, e_i = 1 or e_i = 2. This yields q|k, i.e., q*t = k. Now for n*k^2 = q*m^3*q^2*t^2 = (q*m)^3 * t^2 to be a cube, t must be a cube. Now, k > n, so q*t/(q*m^3) = t/m^3. The least cube > m^3 is (m+1)^3 so k = q*(m+1)^3 which completes the proof. - David A. Corneth, Nov 03 2016

			a(24) = 81  because 24 *  81^2 =  54^3;
a(25) = 200 because 25 * 200^2 = 100^3;
a(26) = 208 because 26 * 208^2 = 104^3;
a(27) = 64  because 27 *  64^2 =  48^3.
The cubefree part of 144 is 18. The cubefull part of 144 is 8 = 2^3. Therefore, a(144) = 18 * 3^3 = 486. - _David A. Corneth_, Nov 01 2016

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000578, A008590, A008834, A048766, A050985, A072905, A254767, A277781.

Cf. A002117, A013662, A013663, A013664.

Table[k = n + 1; While[! IntegerQ[(n k^2)^(1/3)], k++]; k, {n, 55}] (* Michael De Vlieger, Nov 04 2016 *)

a(n) = {my(k = n+1); while (!ispower(n*k^2, 3), k++); k;} \\ Michel Marcus, Oct 31 2016

a(n) = {my(f = factor(n)); f[, 2] = f[, 2]%3; f=factorback(f); n = sqrtnint(n/f,3); (n+1)^3 * f} \\ David A. Corneth, Nov 01 2016

a(n) = A050985(n) * A000578(1+A048766(A008834(n))). [Formula given in comments expressed with A-numbers] - Antti Karttunen, Nov 02 2016.

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 + (3*zeta(4) + 3*zeta(5) + zeta(6))/zeta(3) = 7.13539675963975495073... . - Amiram Eldar, Feb 17 2024

A278818 a(n) is the least k > n such that k + n is square.

Original entry on oeis.org

1, 3, 7, 6, 5, 11, 10, 9, 17, 16, 15, 14, 13, 23, 22, 21, 20, 19, 31, 30, 29, 28, 27, 26, 25, 39, 38, 37, 36, 35, 34, 33, 49, 48, 47, 46, 45, 44, 43, 42, 41, 59, 58, 57, 56, 55, 54, 53, 52, 51, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 83, 82, 81, 80, 79, 78

Offset: 0

Peter Kagey, Nov 28 2016

			a(1) = 3 because 1 + 3 = 4 is square, but 1 + k is not square for 1 < k < 3.
a(2) = 7 because 2 + 7 = 9 is square, but 2 + k is not square for 2 < k < 7.
a(3) = 6 because 3 + 6 = 9 is square, but 3 + k is not square for 3 < k < 6.

Peter Kagey, Table of n, a(n) for n = 0..10000

Cf. A072905.

A278818:=n->ceil(sqrt(2*n+1))^2-n: seq(A278818(n), n=0..100); # Wesley Ivan Hurt, Dec 01 2016

f[n_] := Ceiling[Sqrt[2 n + 1]]^2 - n; Array[f, 70, 0] (* Robert G. Wilson v, Nov 28 2016 *)

def a(n)
  (n + 1..Float::INFINITY).find { |i| n + i == ((n + i)**0.5).to_i**2 }
end

a(n) = ceiling(sqrt(2n+1))^2 - n. - Jon E. Schoenfield, Nov 28 2016

cp's OEIS Frontend

A255167 a(n) = A072905(n) - A006255(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A305677 Number of subsets of {n+1, n+2, ..., A072905(n)-1} whose product has the same squarefree part as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A086481 Erroneous version of A072905.

Views

Author

Keywords

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A066400 Smallest values of t arising in R. L. Graham's sequence (A006255).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Extensions

A254732 a(n) is the least k > n such that n divides k^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Ruby

Formula

A254767 a(n) is the least k > n such that k*n is a cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Ruby

A277781 a(n) is the least k > n such that n*k or n*k^2 is a cube.

Views

Author

Keywords

Comments

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_1b_2...*b_t is a perfect square.

A277781 a(n) is the least k > n such that nk or nk^2 is a cube.