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.

%I A307092 #56 Jan 11 2021 22:59:56
%S A307092 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,
%T A307092 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,
%U A307092 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
%N 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.
%C A307092 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]
%C A307092 From _Peter Kagey_ and Chris Quisling, Aug 22 2019: (Start)
%C A307092 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.
%C A307092 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.
%C A307092 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.
%C A307092 For example, running "/execute at @e run execute at @e run summon minecraft:cat" places x^2 new creatures into the game.
%C A307092 (End)
%C A307092 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
%H A307092 Peter Kagey, <a href="/A307092/b307092.txt">Table of n, a(n) for n = 1..10000</a>
%H A307092 Ely Golden, <a href="/A307092/a307092_1.py.txt">Python program for generating terms of this sequence</a>
%H A307092 Minecraft Wiki, <a href="https://minecraft.gamepedia.com/Commands/execute">Execute command</a>
%e A307092 For n = 43, a(43) = 4 because we can reach 43 by the four iterations below, but not in less iterations:
%e A307092 - 1 -> 2 by setting j=0, 1 + 1^0 = 2,
%e A307092 - 2 -> 6 by setting j=2, 2 + 2^2 = 6,
%e A307092 - 6 -> 42 by setting j=2, 6 + 6^2 = 42,
%e A307092 - 42 -> 43 by setting j=0, 42 + 42^0 = 43.
%e A307092 From _Peter Kagey_, Aug 22 2019: (Start)
%e A307092 So if there is exactly one creature in the game, running the following four commands will result in 43 creatures in the game:
%e A307092 /summon minecraft:cat
%e A307092 /execute at @e run execute at @e run summon minecraft:cat
%e A307092 /execute at @e run execute at @e run summon minecraft:cat
%e A307092 /summon minecraft:cat
%e A307092 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.
%e A307092 (End)
%t A307092 (* To get more terms of the sequence, increase terms, maxa and maxx, and then set maxi=trunc(lb(maxx)) *)
%t A307092 maxi=16; maxx=65536; maxa=10; terms=100;
%t A307092 a = NestList[
%t A307092   Function[list,
%t A307092    DeleteDuplicates[
%t A307092     Join[list,
%t A307092      Flatten[Table[If[# + #^i <= maxx, # + #^i, 1], {i, 0, maxi}] & /@
%t A307092        list]]]], {1}, maxa];
%t A307092 b = Prepend[Table[Complement[a[[i + 1]], a[[i]]], {i, Length[a] - 1}],
%t A307092    First[a]];
%t A307092 c = SparseArray[
%t A307092    Flatten[b] ->
%t A307092     Flatten[Table[
%t A307092       ConstantArray[i, Length[b[[i]]]], {i, Length[b]}]]] // Normal;
%t A307092 Take[c, terms] - 1
%Y A307092 Cf. A000523, A307074.
%K A307092 nonn
%O A307092 1,3
%A A307092 _Yancheng Lu_, Mar 24 2019