A307074 -id:A307074 - cp's OEIS frontend

A307092 a(n) is the minimum number of iterations of the form x -> x + x^j (where j is a nonnegative integer and need not be identical in each iteration) required to reach n starting from 1.

0, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 4, 5, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 3, 4, 5, 6, 2, 3, 3, 4, 4, 5, 4, 5, 3, 4, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 6, 7, 4, 5, 5, 6, 6, 7, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 3, 4, 5, 6, 6, 7, 5, 6, 7, 8, 8, 9, 6, 7, 7, 8, 7

Offset: 1

Yancheng Lu, Mar 24 2019

nonn

The background of this sequence is an "execute-summon" problem in Minecraft command system ver. 1.13+. In Minecraft v1.13+, if you just summon an entity using the "summon" command, you get one more. However, when you combine the "summon" command with nested "execute" commands that target all entities, you will get x^j more entities, where x is the number of entities before the command and j is the number of times the command is nested. To obtain a given number of entities, we are interested in the minimal number of iterations using such commands. The minimal number of iterations to get n is the n-th term of this sequence. [Clarified by Peter Kagey, Aug 24 2019]
From Peter Kagey and Chris Quisling, Aug 22 2019: (Start)
In Minecraft there are several commands, such as /summon, which summons a creature, and /execute which can be combined with other commands to behave like a for-loop.
For example, running "/summon minecraft:cat" places a cat into the game, and running "/execute at @e run summon minecraft:cat" places one cat into the game for every creature in the game.
If there are x creatures in the game, nesting the "execute" command k times has the effect of creating x^k new creatures, resulting in a total of x + x^k creatures.
For example, running "/execute at @e run execute at @e run summon minecraft:cat" places x^2 new creatures into the game.
(End)
a(n) <= 2*A000523(n), as we can always get from floor(n/2) to n by applying the map(s) x -> x + x (and x -> x + 1 if n is odd). - Ely Golden, Aug 19 2020

			For n = 43, a(43) = 4 because we can reach 43 by the four iterations below, but not in less iterations:
- 1 -> 2 by setting j=0, 1 + 1^0 = 2,
- 2 -> 6 by setting j=2, 2 + 2^2 = 6,
- 6 -> 42 by setting j=2, 6 + 6^2 = 42,
- 42 -> 43 by setting j=0, 42 + 42^0 = 43.
From _Peter Kagey_, Aug 22 2019: (Start)
So if there is exactly one creature in the game, running the following four commands will result in 43 creatures in the game:
/summon minecraft:cat
/execute at @e run execute at @e run summon minecraft:cat
/execute at @e run execute at @e run summon minecraft:cat
/summon minecraft:cat
Which have 0, 2, 2, and 0 nested "execute" commands respectively, and four is the fewest number of commands that can be run to create exactly 43 creatures in the game.
(End)

Peter Kagey, Table of n, a(n) for n = 1..10000
Ely Golden, Python program for generating terms of this sequence
Minecraft Wiki, Execute command

Cf. A000523, A307074.

(* To get more terms of the sequence, increase terms, maxa and maxx, and then set maxi=trunc(lb(maxx)) *)
maxi=16; maxx=65536; maxa=10; terms=100;
a = NestList[
  Function[list,
   DeleteDuplicates[
    Join[list,
     Flatten[Table[If[# + #^i <= maxx, # + #^i, 1], {i, 0, maxi}] & /@
       list]]]], {1}, maxa];
b = Prepend[Table[Complement[a[[i + 1]], a[[i]]], {i, Length[a] - 1}],
   First[a]];
c = SparseArray[
   Flatten[b] ->
    Flatten[Table[
      ConstantArray[i, Length[b[[i]]]], {i, Length[b]}]]] // Normal;
Take[c, terms] - 1

A309978 a(n) is the number of positive integers k such that there exists a nonnegative integer m with k + k^m = n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1

Offset: 1

Peter Kagey, Aug 28 2019

nonn

Records occur at 1, 2, 4, 6, 30, ...

Does there exist n such that a(n) >= 5? Do there exist examples besides 30 and 130 such that a(n) = 4? If so in either case, n > A253913(10000) = 87469256.

			For n = 130 the a(130) = 4 positive integers with valid maps are
  129 via 129 + 129^0 = 130,
   65 via  65 +  65^1 = 130,
    5 via   5 +   5^3 = 130, and
    2 via   2 +   2^7 = 130.

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

Cf. A253913, A307074, A307092, A309997.

a(n) = {if (n==1, return (0)); my(d = divisors(n)); 1 + sumdiv(n, d, if ((d>1) && (dMichel Marcus, Oct 16 2019

a(2n+1) = 1 for all n >= 1.

a(2n) >= 2 for all n >= 2.

A309997 Number of paths from 2 to n of length A307092(n) - 1 via maps of the form x -> x + x^j, where j is a nonnegative integer.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2

Offset: 2

Peter Kagey, Aug 26 2019

nonn

This sequence counts paths starting from 2 since there are an infinite number of maps from 1 to 2 via 1 -> 1 + 1^j.

Records occur at 2, 12, 226, 372, 744, 1490, 139511, ...

			For n = 520, the a(520) = 3 sequences of A307092(520)-1 = 3 maps are:
2 -> 2 + 2^1 -> 4 + 4^1     -> 8 + 8^3     = 520
2 -> 2 + 2^1 -> 4 + 4^4     -> 260 + 260^1 = 520
2 -> 2 + 2^7 -> 130 + 130^1 -> 260 + 260^1 = 520
With exponents (1,1,3), (1,4,1), and (7,1,1) respectively.

Peter Kagey, Table of n, a(n) for n = 2..10000
Peter Kagey, Count the number of paths to n, Code Golf Stack Exchange.

Cf. A307074, A307092.

A328422 Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 14, 14, 18, 18, 24, 24, 31, 31, 42, 42, 51, 51, 65, 65, 79, 79, 97, 97, 118, 118, 142, 142, 167, 167, 198, 198, 229, 229, 271, 271, 317, 317, 368, 368, 419, 419, 484, 484, 549, 549, 628, 628, 707, 707, 808, 808, 905, 905, 1023

Offset: 2

Peter Kagey, Oct 15 2019

nonn

This sequence is essentially the same as the number of paths from 1 to n. However, starting from 2 removes the ambiguity of how many maps there are from 1 to 2.

a(2n+1) = a(2n) for all n because x + x^j is odd if and only if x is even and j = 0.

			For n = 8 the a(8) = 6 paths are:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 with j = [0,0,0,0,0,0]
2 -> 3 -> 4 -> 8                with j = [0,0,1]
2 -> 3 -> 6 -> 7 -> 8           with j = [0,1,0,0]
2 -> 4 -> 5 -> 6 -> 7 -> 8      with j = [1,0,0,0,0]
2 -> 4 -> 8                     with j = [1,1]
2 -> 6 -> 7 -> 8                with j = [2,0,0]

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

Cf. A307074, A307092, A309997, A309978.

a(2) = 1, a(n) = Sum_{k=1..A309978(n)} a(A328446(n,k)) for n > 2.

cp's OEIS Frontend

A307092 a(n) is the minimum number of iterations of the form x -> x + x^j (where j is a nonnegative integer and need not be identical in each iteration) required to reach n starting from 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A309978 a(n) is the number of positive integers k such that there exists a nonnegative integer m with k + k^m = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A309997 Number of paths from 2 to n of length A307092(n) - 1 via maps of the form x -> x + x^j, where j is a nonnegative integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A328422 Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula