How Many 8's?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
using namespace std;

unsigned long long eightnew(int n)
{
     unsigned long long i,a=(ceil(pow(10,n))-1)*8/9,b=ceil(pow(10,n)),k;
    for(i=2;;i+=10)
    {
        k=i*i*i;
        k=k%b;
        if(k==a)return i;
    }
}
int main()
{
    long long s=0;
    for(int n=1;n<=8;n++)
    {
    s+=eightnew(n);
    }
    cout<<s/2<<endl;
}

bro, can you help? i don't find any fault in my code.

As Calvin points out, a number-theoretic approach to this problem provides a more efficient solution. Here's one that I implemented:

Define $P(n):=\{x\mid x^3\equiv\underbrace{88\ldots 88}_{n\textrm{ times}}\pmod{10^n}\}$ .

First, we note two things:

1) $a\in P(n)\implies a\in P(n-1)~\forall~n\geq 2$ (obvious)

2) $\forall~n\geq 1~,~a\notin P(n)~\forall~0\lt a\leq 10^n\implies P(n)=\emptyset$ (since $x^m\equiv (x~\bmod~10^n)\pmod{10^n}$ )

Combining these two things, we can see that finding $P(1)$ is easy by just testing the values less than $10$ and $\forall~n\geq 1$ , after finding $P(n)$ , to find $P(n+1)$ , we just need to test the values $a$ which are $\lt 10^n$ and $a~\bmod~10^n\in P(n)$ . If no solutions are found in a particular iteration, that means no further solutions exist.

So, we implement this in python as follows (using res for $P(n)$ and resn for $P(n+1)$ )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from itertools import count                                 #non-negative integer generator
def test(x,m,a,n):                                          
    return pow(x,m,10**n)==int(str(a)*n)                    #x^m = a (mod 10^n) test

def method(a,m,s):                                          #a is 1-digit and method prints the smallest solutions to x^m = a (mod 10^n) for n=1 to s
    res=[i for i in range(10) if test(i,m,a,1)]; resn=[]    #res is the old solution basis and resn is the new solution basis
    if res==[]:                                             #old solution basis is empty, so no (further) solutions possible
        print('No solutions possible')
        return
    else: print(res[0])                                     #else res[0] is the minimum solution when n=1
    for n in range(2,s+1):                                  #loop for s solutions, is executed when s>1
        for i in res:
            for p in count():
                xn=int(str(p)+str(i))                       #possible solution generated from old solution basis res
                if xn>=10**n: break                         #values xn greater than modulo are solutions iff xn mod 10**n is a solution, so no need to test bigger values, so break
                if test(xn,m,a,n): resn.append(xn)          #if it's a solution, append it to resn, the new solution basis for next iteration
        if resn==[]:
            print('No further solutions possible, all %d solutions generated' %(n-1))
            return
        else:
            res=resn[:]                                     #copy resn to res for next iteration basis
            print(min(res))                                 #print the smallest solution found in current iteration
            resn=[]                                         #clear resn for next iteration

method(8,3,8)                                               #call to method for first 8 solutions to x^3 = 88..88 (n times)  (mod 10^n)

In fact, the above code provides an efficient (more or less) solution to a more general problem, i.e., method(a,m,s) solves the problem of finding the smallest positive integer solutions to $(x_n)^m\equiv\underbrace{aa\ldots aa}_{n\textrm{ times}}\pmod{10^n}~\forall~1\leq n\leq s$ where $1\leq a\leq 9$ and $m\geq 1$ .