Does every number base have at least one "Baseless number"?

Question

Definition & questions

Every number $a \in N$ can be written in some integer number base $b \geq 2$ using $d$ -digits:

\begin{aligned} a & = {\bar{(a_{1}, a_{2}, \dots, a_{d - 1}, a_{d})}}_{b} \\ = a_{1} b^{d - 1} + a_{2} b^{d - 2} + a_{3} b^{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{aligned}

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 $base$ , with multiplications with the $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) 10 + 3) 10 + 8) 10 + 5) = ((((8) 8 + 3) 3 + 8) 8 + 5) 5 = f_{10} (8385)

From now on, assume $a \geq 2$ because $1$ is trivially baseless in all number bases.

I have two questions. Firstly and mainly,

$1.$ Existence: Does every number base $b \geq 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) \neq 0$ for all $a \geq 2$ other than $a = 8385$ ?

I have looked at which point will $E (a) > 0$ for all $a > 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} < l_{b}$ . For $b = 10$ we have:

$\frac{9}{8} (- 1 + 9^{d + 1}) < \frac{1}{9} (- 1 + 10^{d}) if d > 42.8266$
That is, we know that if $a$ has $d \geq 43$ digits, then $f_{10} (a)$ has less than $d$ digits. In other words, we have $f_{10} (a) < a$ , implying $E_{10} (a) > 0$ for all $a \geq 10^{42}$ .

This means if there is a second solution for the decimal number base, it must be $a < 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 \leq 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) > 0$ ). Hence from now on, assume $b \geq 4$ .

Does every number base $b \geq 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:

\begin{matrix} (⋆) & a = \sum_{i = 1}^{d} a_{i} b^{d - i} = \sum_{i = 1}^{d} a_{i}^{2} \prod_{j = i + 1}^{d} a_{j} = f_{b} (a) \end{matrix}

In digits $0 < a_{1}, \dots, a_{d} < b$ . The question is now, is it true that:

For all $b \geq 4$ there exists $d \geq 2$ such that $(⋆)$ 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 = {\bar{(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 $(⋆)$ we get $a_{1} b + a_{2} = a_{1}^{2} a_{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 ${\bar{(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 \geq 4$ have at least one solution for at least one $d \geq 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 > 107^{6} > 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$ ?

Some more smallest examples: $[56, 1044820] [53, 1080289] [95, 2757742] [97, 16316136] [83, 17926545] [69, 22505500]$ . Bases $43$ and $73$ have no solutions below $2^{31}$ . — nickgard
– nickgard, Commented May 4, 2020 at 16:53
I had an overflow bug when I reversed the digits to do the calculation! It didn't affect relatively low numbers, so all the results in the previous comment are correct, but $43$ does in fact have a solution below $2^{31}$ . $[43, 1593074855] [73, 25683204625]$ . The number must be divisible by its last digit in the relevant base, so that provides a small speed-up to the search. — nickgard
– nickgard, Commented May 5, 2020 at 10:18
@nickgard Thank you. You motivated me to rewrite my code from Mathematica to C++ and I can now confirm your results for $43, 73$ . (Now it takes me around $60$ seconds on my laptop to check $10^{9}$ numbers for some base $b$ - so $73$ took me about $25$ minutes now.) — Vepir
– Vepir, Commented May 5, 2020 at 12:29
"Baseless" is sort of an odd name for this because it suggests some kind of base invariance, but this concept is relative to a specific base. It's strange to call something "base-10 baseless". — Jack M
– Jack M, Commented May 8, 2020 at 17:00

Vepir · Accepted Answer · 2020-05-08 17:39:21Z

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) \leq 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 \dots 999$ and start lowering the first digit until it is some $x_{1}$ , until $a - f_{10} (a) \leq 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) > 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) \leq 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) \leq 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 \geq 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)) \leq 0$ is no longer true. Another optimization could be to optimize the check for the $(a - f_{b} (a)) \leq 0$ 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 \leq 13$ . 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 \leq 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

Bases that have exactly one baseless number: ${6, 10, \dots}$ . The next term is $\geq 38$ (If the next term is not $38$ , then base $38$ should have at least one $d \geq 8$ example, because for $d < 8$ it has one solution only.) — Vepir
– Vepir, Commented May 9, 2020 at 15:02
Are you aware of the fractal structure of your graph? Each next waterfall seems to be an expanded copy of the previous and also similar to its stretched copy. — Alex Ravsky
– Alex Ravsky, Commented May 30, 2020 at 6:08

Stack Exchange Network

Does every number base have at least one "Baseless number"?

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Strictly Necessary Cookies

Performance Cookies

Functional Cookies

Targeting Cookies

Does every number base have at least one "Baseless number"?

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions