Does every number base have at least one "Baseless number"?
Definition & questions
Every number $a\in\mathbb N$ can be written in some integer number base $b\ge 2$ using $d$-digits: $$\begin{align} a &=\overline{(a_1,a_2,\dots ,a_{d-1},a_{d})}_b\\ &=a_1b^{d-1}+a_2b^{d-2}+a_3b^{d-3}+\dots+a_{d-2}b^2+a_{d-1}b^1+a_{d}b^0\\ &=(((\dots(((a_1)b+a_2)b+a_3)b+\dots)b+a_{d-2})b+a_{d-1})b+a_{d} \end{align}$$
If we multiply the last expression by $b$, then replace all $b$'s with $a_1,\dots,a_d$, we get $f_b(a)$.
(We replaced the multiplications with the $\text{base}$, with multiplications with the $\text{digits}$.)
If it holds $a=f_b(a)$, then we call number $a$ an "Baseless number (in base $b$ )".
For example, $8385$ is a $4$-digit Baseless number in base $10$ (decimal number base), because:
$$ 8385=((((8)\color{red}{10}+3)\color{red}{10}+8)\color{red}{10}+5)=((((8)\color{blue}{8}+3)\color{blue}{3}+8)\color{blue}{8}+5)\color{blue}{5}=f_{10}(8385) $$
From now on, assume $a\ge2$ because $1$ is trivially baseless in all number bases.
I have two questions. Firstly and mainly,
$1.$ Existence: Does every number base $b\ge 4$ contain at least one Baseless number?
- Status: Currently $b=107$ is the smallest base with no known examples.
Secondly and supplementary,
$2.$ Solving decimal base: Is number $8385$ the only decimal Baseless number?
- Solved: This was now proven to be true by an exhaustive search.
$2.$ Baseless numbers in decimal number base
Is number $8385$ the only decimal Baseless number?
I've checked this up to $10^{10}$ so far, and found no other examples.
Scatter-plotting the "error" $E_{10}(a)=(a-f_{10}(a))$ for $a\in[1, 10^6]$ we have:
A graph filled with Waterfall structures.
Can we prove that $E_{10}(a)\ne 0$ for all $a\ge 2$ other than $a=8385$ ?
I have looked at which point will $E(a)\gt 0$ for all $a\gt a_0$ for some $a_0$:
We know that $f_{b}(a)$ of a $d$-digit number is at most $u_b(d)=\sum_{i=1}^{d+1}(b-1)^{i}$, the case when all digits are set to $(b-1)$, the largest base $b$ digit. We also know that a $d$-digit number is at least $l_b(d)=b^{d-1}$. But notice that we can't have a zero digit in the number $a$ because then $f_b(a)$ automatically has less digits than $a$, so we can improve the lower bound to $l_b(d)=\sum_{i=1}^{d}b^{d-i}$.
-
Hence, we try to find all $d$ for which $u_b\lt l_b$. For $b=10$ we have:
$$\frac98 (-1 + 9^{d+1})\lt\frac19 (-1 + 10^d) \space\space\text{ if }\space\space d\gt 42.8266$$
That is, we know that if $a$ has $d\ge43$ digits, then $f_{10}(a)$ has less than $d$ digits. In other words, we have $f_{10}(a)\lt a$, implying $E_{10}(a)\gt 0$ for all $a\ge 10^{42}$.
This means if there is a second solution for the decimal number base, it must be $a \lt 10^{42}$.
That is, so far I have that if there is a second example, it is $a\in[10^{10},10^{42}]$.
Can we somehow lower this bound or remove significant families of numbers from it?
Update:
Turns out an exhaustive computer search is possible on small bases.
All number bases $b\le 13$ are solved now. I've posted this result as my own partial answer.
$1.$ Existence in other number bases
It is not hard to see that $b=2$ has no examples, and for $b=3$ we can prove there are no examples by checking all numbers up to $10^5$. (Following the bound given in the previous section, larger numbers than this have $E_3(a)\gt 0$). Hence from now on, assume $b\ge 4$.
Does every number base $b\ge 4$ contain at least one Baseless number?
It appears every base has a very small amount in total, if any.
Generally, to solve for all $d$ digit examples in base $b$, we have the Diophantine equation:
$$ a=\sum_{i=1}^{d} a_{i}b^{d-i} = \sum_{i=1}^{d}a_i^2\prod_{j=i+1}^da_j = f_b(a)\tag{$\star$} $$
In digits $0\lt a_1,\dots,a_d\lt b$. The question is now, is it true that:
For all $b\ge 4$ there exists $d\ge 2$ such that $(\star)$ has at least one solution for the digits?
For example, if the number base is a perfect square $b=r^2$, then we have a trivial $2$-digit example: $$ a=\overline{(1,\sqrt{b})}_b=((1) b+\sqrt{b})=((1) 1 + \sqrt{b})\sqrt{b}=f_b(a) $$
This is because if we set $d=2$ in $(\star)$ we get $a_1b + a_2 = a_1^2a_2+a_2^2$. Now specially for $a_1=1$ it reduces to $a_2^2=b$ implying that if $b$ is a perfect square, then the number $\overline{(1,\sqrt{b})}_b=b+\sqrt{b}$ is a Baseless number in the base $b$.
If we look at $d=2$ in general, all solutions below base $100$ are in this pastebin table $(d=2)$.
If we look at $d=3$, almost all bases below $100$ have one or more $3$-digit Baseless number examples. You can see the list of all solutions in this pastebin table $(d=3)$.
And so on. But does every base $b\ge 4$ have at least one solution for at least one $d\ge 2$ ?
I started searching for "smallest example per number base".
The record bases with next largest smallest example are: (Thank you nickgard.)
base example digits in base
4 6 [ 1, 2 ]
5 12 [ 2, 2 ]
6 160 [ 4, 2, 4 ]
7 324 [ 6, 4, 2 ]
8 405 [ 6, 2, 5 ]
10 8385 [ 8, 3, 8, 5 ]
18 25215 [ 4, 5, 14, 15 ]
24 323844 [ 23, 10, 5, 12 ]
32 1038448 [ 31, 22, 3, 16 ]
43 1593074855 [ 10, 35, 41, 39, 11, 19 ]
73 25683204625 [ 12, 28, 28, 56, 52, 65 ]
107 ? ?
The smallest example for base $107$ is $a \gt 107^{6}\gt 1.5\cdot 10^{12}$, so far.
Other bases below $500$ that do not have any examples below $10^{10}$ are:
191,227,307,331,373,386,398,411,421,431,467,471,485
For bases below $500$ with known smallest solutions, see this pastebin table.
Is it possible to optimize the search for the smallest Baseless number in some base $b$?
I haven't made any progress in answering the first question, but I solved the second question.
That is, I computationally (by exhaustive search) prove that:
The number $8385$ is indeed the one and only decimal baseless number.
For the decimal base $(b=10)$, it is sufficient to check only a small fraction of numbers in the interval $[11,10^{22}]$. In fact, this amount is so small that it is doable in few seconds.
The idea is to check only intervals where there exist numbers such that $E_b(a)\le 0$. (where $E_b(a)=a-f_b(a)$ is defined in the original question)
For example, if $b=4$, instead of checking all numbers in $[5,4^{d_0}]$ where $d_0$ is sufficiently large, we can simply check only those in the highlighted intervals:
Algorithm to find the highlighted intervals
For example, to find all $d$ digit solutions for base $b=10$, we start with a $d$-digit number $999\dots999$ and start lowering the first digit until it is some $x_1$, until $a-f_{10}(a)\le 0$ is no longer true. We discard all numbers whose first digit is smaller than some $x_1$ because they satisfy $a-f_{10}(a)\gt 0$ and hence can't be a solution.
This leaves us with numbers whose first digit is $\in[x_1,9]$. (We found lower bound for the first digit.) We repeat this process for each possible case of the first digit, but now we decrease the second digit until $a-f_{10}(a)\le 0$ is no longer true.
This gives us numbers whose second digit is $\in[x_2(x'_1),9]$ for each fixed choice of the first digit $x'_1\in[x_1,9]$. (We found lower bounds for the second digit depending on the first digit.)
Now we move onto the third digit to find lower bounds on the third digit depending on what is the second and first digit, and so on.
We repeat this process until we reach the unit digit lower bound $\in[x_d(x'_1,x'_2,\dots,x'_{d-1}),9]$, where $x_d$ depends on all previous digit choices $x'_1,x'_2,\dots,x'_{d-1}$. In this last step, we have all numbers $a$ for which we have $a-f_{10}(a)\le 0$. To find solutions, we check for which numbers the equality holds $a-f_{10}(a)=0$.
For large enough $d_0$, we get $0$ intervals in the first step so we can eliminate all such $d\ge d_0$.
This works because we are simply discarding intervals of numbers for which $a-f_{10}(a)$ is strictly positive. Such numbers $a$ are all larger than the $f_{10}(a)$ and can't be a solution.
For larger bases $b$ than $10$, this can be optimized by preforming a binary search on the digit at each step, instead of linearly decreasing the largest digit until $(a-f_b(a))\le0$ is no longer true. Another optimization could be to optimize the check for the $(a-f_b(a))\le0$ condition itself. But I haven't bothered with such or similar optimizations because this is already good enough to answer the $b=10$ case.
Here is a quick hack of the idea that I used to fully solve $b=10$ and other small bases:
("cases" is only the number of numbers iterated in the last step of the segment division)
#include <iostream>
#include <vector>
#include <ctime>
#include <limits>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef unsigned int digit_;
typedef std::vector<digit_> digitV_;
typedef boost::multiprecision::int256_t number_;
const number_ number__max = std::numeric_limits<number_>::max();
const digit_ digit__max = std::numeric_limits<digit_>::max();
void printLocalTime() {
time_t t = time(0);
tm* now = localtime(&t);
cout << (now->tm_hour + 0) << ':'<< (now->tm_min + 0) << ':'<< now->tm_sec;//<< endl;
}
void print(digitV_ digits) {
cout << "[ ";
for(int i = 0; i < digits.size(); i++) {
cout << digits[i] << " ";
}
cout <<"]";
}
number_ nval(digit_ base, digitV_& digits) {
number_ n = 0;
for(int i = 0; i < digits.size(); i++) {
n += digits[i];
n *= base;
}
n /= base;
return n;
}
number_ fval(digit_ base, digitV_& digits) {
number_ n = 0;
for(int i = 0; i < digits.size(); i++) {
n += digits[i];
n *= digits[i];
}
return n;
}
number_ totcases = 0;
number_ cases = 0;
bool brnary(digit_ base, digitV_ &digits, digit_ step = 0) {
//if (step<=3 && digits.size()>= 4) {print(digits); cout << " ("; printLocalTime(); cout << ") " << endl;}
bool found = false;
digit_ _digit = digits[step];
for (digit_ dlast = base-1; dlast > 0; dlast--) {
digits[step] = dlast;
/** iterating solution segment for solutions **/
if (step == digits.size()-1) {
cases += 1;
totcases += 1;
number_ neval = nval(base, digits);
number_ feval = fval(base, digits);
if (neval == feval) {
cout << base << " " << nval(base, digits) << " ";
print(digits); cout << endl;
found = true;
} else if (neval > feval) {
break;
}
/** recursively entering potential solution segments **/
} else {
if (nval(base, digits) <= fval(base, digits)) {
found = brnary(base, digits, step+1) || found;
} else {
break;
}
}
}
digits[step] = _digit;
return found;
}
int main() {
cout << "limits: number__max(" << number__max << "), digit__max(" << digit__max << "). "; printLocalTime(); cout << endl;
int bstart;
cout << "starting base = ";
cin >> bstart;
for (digit_ base=bstart; base<digit__max; base++) {
cout << "\nbase " << base << ": " << endl;
totcases = 0;
for (digit_ d=2; d<=digit__max; d++) {
cout << "digits " << d << ": ("; printLocalTime(); cout << ") " << endl;
cases = 0;
digitV_ digits(d, base-1);
if (brnary(base, digits)) {}//break;}
cout << "cases: " << cases << endl;
if (cases == 0) {break;}
}
cout << "total cases: " << totcases << endl;
}
return 0;
}
But the complexity of this algorithm still grows more than exponentially, relative to the largest digit case $d$ we need to check, which grows relative to base $b$.
For $b=13$, it already takes up to an hour to check all possible candidates for all solutions. At the end, I've included all baseless numbers for bases $b\le13$. So this only works in reasonable time for very small bases $b$, which is sufficient to fully solve the $b=10$ case.
Here are all solutions for baseless numbers for bases $b\le 13$ :
("numbers checked" only counts "cases" from the last step of the algorithm)
base 4:
6 [ 1 2 ]
46 [ 2 3 2 ]
27 [ 1 2 3 ]
numbers checked: 31
base 5:
12 [ 2 2 ]
64 [ 2 2 4 ]
numbers checked: 133
base 6:
160 [ 4 2 4 ]
numbers checked: 649
base 7:
324 [ 6 4 2 ]
928 [ 2 4 6 4 ]
numbers checked: 3547
base 8:
405 [ 6 2 5 ]
11645 [ 2 6 5 7 5 ]
numbers checked: 22298
base 9:
21 [ 2 3 ]
12 [ 1 3 ]
196 [ 2 3 7 ]
2172 [ 2 8 7 3 ]
2075 [ 2 7 5 5 ]
29869 [ 4 4 8 6 7 ]
numbers checked: 157677
base 10:
8385 [ 8 3 8 5 ]
numbers checked: 1267736
base 11:
36 [ 3 3 ]
1257 [ 10 4 3 ]
405 [ 3 3 9 ]
11225 [ 8 4 8 5 ]
numbers checked: 11160271
base 12:
189 [ 1 3 9 ]
9738 [ 5 7 7 6 ]
2673 [ 1 6 6 9 ]
1677823 [ 6 8 10 11 6 7 ]
numbers checked: 105405889
base 13:
1484 [ 8 10 2 ]
784 [ 4 8 4 ]
numbers checked: 1076880407