Let $n$ is integer and we want to express it in terms of $10$ as $$n=R^3_k10^k+R^3_{k-1}10^{k-1} \cdots+ R^3_0$$ where $R_i\in \{\pm0,\pm 1,\pm 2,\ldots,\pm9\}$
Example : $37= 1^3\times10+3^3$
Algorithms: Let $$ n = Q_0 \cdot 10+R^3_0, $$
where $ |R_0| < 10$. Then, we can in turn represent
$$ Q_0 = Q_1 \cdot 10 + R^3_1, $$
where $ |R_1| < 10 $, and so on, so we can find $R_0, R_1, \dots$ with consecutive division by $10$ and taking remainders.
\begin{equation*} \begin{split} n&=Q_0\cdot 10+R^3_0 \\ Q_0&= Q_1\cdot 10+R^3_1 \\ Q_1&= Q_2\cdot 10+R^3_2 \\ \vdots &=\quad \vdots\\ Q_{k-2} &= Q_{k-1}\cdot 10+R^3_{k-1}\\ Q_{k-1} &= 0\cdot f + R^3_{k} \end{split} \end{equation*}
where $R_i\in \{\pm0,\pm 1,\pm 2,\ldots,\pm9\}$
Hence, $n=(R^3_k,R^3_{k-1}, \cdots, R^3_0)_{10}\quad \text{or simply} \quad [R_k,R_{k-1}, \cdots, R_0]$
Note: For each $Q$ there are $R^3$ and $-R^3_*$ such that $Q\equiv R^3\equiv -R^3_*\pmod{10}$
Example: \begin{equation*} \begin{split}531&=2^3\times 10^2+(-3)^3\times 10+1^3\\ &=(2^3,-3^3,1^3)_{10}\\ &=[2,-3,1] \end{split} \end{equation*}
here representation is not unique. for example
\begin{equation*} \begin{split}531 &=(2^3,-3^3,1^3)_{10}\\ &=(1^3,-2^3,-1^3,-4^3,-9^3)_{10}\\ &=[1,-2,-1,-4,-9] \end{split} \end{equation*}
Define function $D(n)$, calculate minimal degree to represent $n$ in terms of $10$ where coefficients are cube number less than $10^3$ and greater than $-10^3$
so $D(531)=2$ because we can express $531=2\times 10^2+(-3)^3\times 10+1^3$ have degree $2$ and smallest representation.
Question: Is there any approach to calculate $D(n)$ in fastest way? if yes, what is it?
Question has already been asked on MathOverflow but no one answers link : https://mathoverflow.net/q/454193/149083 I have not been able to complete program which verify the shortest representation. How to solve loop problem in code. If you make please share your code. thank you in advanced. Here what I attempt in code,
def d2(y):
res = []
for p in range(15):
if y > 0:
if y%10 == 0:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 1:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 2:
k = 10 - y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 3:
k = 10 - y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 4:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 5:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 6:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 7:
k = 10 - y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 8:
k = 10 - y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 9:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y < 0:
if y%10 == 0:
k = y%10
res.append(k)
y = (y-k**3)//10
elif y%10 == 9:
res.append(-1)
y = (y+1**3)//10
elif y%10 == 8:
res.append(-8)
y = (y+8**3)//10
elif y%10 == 7:
res.append(-7)
y = (y+7**3)//10
elif y%10 == 6:
res.append(-4)
y = (y+4**3)//10
elif y%10 == 5:
res.append(-5)
y = (y+5**3)//10
elif y%10 == 4:
res.append(-6)
y = (y+6**3)//10
elif y%10 == 3:
res.append(-3)
y = (y+3**3)//10
elif y%10 == 2:
res.append(-2)
y = (y+2**3)//10
elif y%10 == 1:
res.append(-9)
y = (y+9**3)//10
if y == 0:
break
if len(res[::-1]) == 15:
return("not get, stuck in a loop, try another number")
else :
return res[::-1]
for i in range(1000,1100):
print(i,d2(i),"\n")
>>> output
1000 [1, 0, 0, 0]
1001 [1, 0, 0, 1]
1002 not get, stuck in a loop, try another number
1003 [1, 1, -5, 6, 7]
1004 not get, stuck in a loop, try another number
1005 [2, 2, 5]
1006 not get, stuck in a loop, try another number
1007 not get, stuck in a loop, try another number
1008 [1, 0, 0, 2]
1009 not get, stuck in a loop, try another number
1010 [1, 0, 1, 0]
1011 [1, 0, 1, 1]
1012 not get, stuck in a loop, try another number
1013 not get, stuck in a loop, try another number
1014 not get, stuck in a loop, try another number
1015 [-4, 9, 5]
1016 [2, 0, 6]
1017 not get, stuck in a loop, try another number
1018 [1, 0, 1, 2]
1019 not get, stuck in a loop, try another number
1020 not get, stuck in a loop, try another number
1021 not get, stuck in a loop, try another number
1022 not get, stuck in a loop, try another number
1023 not get, stuck in a loop, try another number
1024 not get, stuck in a loop, try another number
1025 not get, stuck in a loop, try another number
1026 [2, 1, 6]
1027 [1, 0, 0, 3]
1028 not get, stuck in a loop, try another number
1029 not get, stuck in a loop, try another number
1030 not get, stuck in a loop, try another number
1031 not get, stuck in a loop, try another number
1032 [-1, 3, -6, 8, 8]
1033 [-1, -1, 5, -6, 9, 7]
1034 not get, stuck in a loop, try another number
1035 not get, stuck in a loop, try another number
1036 not get, stuck in a loop, try another number
1037 [1, 0, 1, 3]
1038 not get, stuck in a loop, try another number
1039 not get, stuck in a loop, try another number
1040 not get, stuck in a loop, try another number
1041 not get, stuck in a loop, try another number
1042 not get, stuck in a loop, try another number
1043 not get, stuck in a loop, try another number
1044 not get, stuck in a loop, try another number
1045 not get, stuck in a loop, try another number
1046 not get, stuck in a loop, try another number
1047 not get, stuck in a loop, try another number
1048 not get, stuck in a loop, try another number
1049 not get, stuck in a loop, try another number
1050 not get, stuck in a loop, try another number
1051 not get, stuck in a loop, try another number
1052 [-1, 4, 8]
1053 not get, stuck in a loop, try another number
1054 not get, stuck in a loop, try another number
1055 [1, 0, -5, 7, 5]
1056 not get, stuck in a loop, try another number
1057 not get, stuck in a loop, try another number
1058 not get, stuck in a loop, try another number
1059 not get, stuck in a loop, try another number
1060 [-1, -1, 6, 0]
1061 [-1, -1, 6, 1]
1062 not get, stuck in a loop, try another number
1063 not get, stuck in a loop, try another number
1064 [1, 0, 0, 4]
1065 not get, stuck in a loop, try another number
1066 not get, stuck in a loop, try another number
1067 not get, stuck in a loop, try another number
1068 [-1, -1, 6, 2]
1069 not get, stuck in a loop, try another number
1070 [2, 3, 0]
1071 [2, 3, 1]
1072 not get, stuck in a loop, try another number
1073 [-3, 7, 7]
1074 [1, 0, 1, 4]
1075 not get, stuck in a loop, try another number
1076 not get, stuck in a loop, try another number
1077 not get, stuck in a loop, try another number
1078 [2, 3, 2]
1079 not get, stuck in a loop, try another number
1080 [1, 0, 2, 0]
1081 [1, 0, 2, 1]
1082 not get, stuck in a loop, try another number
1083 [1, 4, 7]
1084 not get, stuck in a loop, try another number
1085 not get, stuck in a loop, try another number
1086 not get, stuck in a loop, try another number
1087 [-1, -1, 6, 3]
1088 [1, 0, 2, 2]
1089 [-1, -2, 6, 9]
1090 [-2, 5, -8, 9, 0]
1091 [-2, 5, -8, 9, 1]
1092 not get, stuck in a loop, try another number
1093 not get, stuck in a loop, try another number
1094 not get, stuck in a loop, try another number
1095 not get, stuck in a loop, try another number
1096 [2, 2, 6]
1097 [2, 3, 3]
1098 [-2, 5, -8, 9, 2]
1099 [1, 3, 9]
One way to compute $D(n)$ is as follows:
From right to left, number the digits of a number as 0, 1, 2, ...
We work from right to left. At step $i$, we have already represented digits 0, 1, $\dots$, $i-1$ of $n$ with a vector $f$ of digits from the set 0, $(\pm 1)^3$, $\dots$, $(\pm 9)^3$, and we wish to represent the digits at and to the left of the digit $i$ in $n$. The vector $f$ may have generated some carries into digit $i$, and we need to take care of those as well.
At step $i$, we have a list of pairs $(f, n')$, each consisting of a vector $f=(f_{i-1},\dots,f_0)$ of already generated output digits together with the number $n'$ which we still need to express. For each pair in the list, we try all possible candidates (either one or two) for the output digit $f_i$ which give the correct result modulo 10. Then, we generate new pairs $((f_i, f_{i-1}, \dots, f_0), (n'-f_i)/10)$ and add them to the list for step $i+1$. If a pair containing $(n'-f_i)/10$ is already in the list, we can either do nothing or replace it with the new pair.
At step 0, the list is initialized with $(\epsilon, n)$, where $\epsilon$ is the empty vector and $n$ is the number we wish to express. We stop at the earliest step when a pair $(f, n')$ with $n'=0$ is in the list and output $f$.
This algorithm does not result in exponential blowup because the carries into digit $i$ are bounded: the generated carries must amount to a sum of strictly less than $$ \sum_{j>0} \frac{9^3}{10^j}=81 $$ and similarly the carries must strictly exceed $-81$. So, the possible values for $n'$ at each step are confined to an interval of length less than $2\cdot 81=162$, meaning that there are never more than 162 entries in the list at any step.
Here is an implementation in Python 3.