Project Euler 346

This problem at first seems more intimidating, but it is enough to realize what are the conditions for a number to be a repunit. Then, just need to optimize by noticing what the boundaries of each base are to reduce the time complexity.

Statement

The number $7$ is special, because $7$ is $111$ written in base $2$, and $11$ written in base $6$ (i.e. $7 _{10} = 11 _{6} = 111 _{2}$). In other words, $7$ is a repunit in at least two bases $b>1$.

We shall call a positive integer with this property a strong repunit. It can be verified that there are $8$ strong repunits below $50$: {$1,7,13,15,21,31,40,43$}.

Furthermore, the sum of all strong repunits below $1000$ equals $15864$.

Find the sum of all strong repunits below $10^{12}$.

Solution

First of all, just take a look that any number $n > 2$ can be written as $11 _{n-1}$. It means that we only need to find another base $m < n-1$, where $n = 11\ldots 11 _{m}$.

Now, this has already covered all the cases when the length of the repunit is $2$, so the next minimum possible length for the repunit is $3$:

\begin{aligned} n = 111_{m} = m^{2}+m+1 \end{aligned}

Using just a raw estimation, we can say that $m < \sqrt{n}$.

The strategy for the solution is just to iterate over all the possible bases $m < \sqrt{n}$, and increasing the length of the repunit, then insert any visited number in a set and take the sum of elements in the set. Time complexity for the search of repunits for a base $m$ is just $O(\log_{m}(n))$, so the total time complexity is just:

\begin{aligned} O(\log(n) \sum_{k=1}^{\sqrt{n}} \frac{1}{\log(k)}) = O(\log(n) \frac{2\sqrt{n}}{\log(n)}) = O(2\sqrt{n}) \end{aligned}

Code

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

#define MAXN 1000000000000
#define N 1000000

set <ll> s;

void solve(){
  for(int base=2; base<=N; base++){
    ll amount = base+1;
    for(int len=2;; len++){
      amount *= base;
      amount++;
      if(amount >= MAXN) break;
      s.insert(amount);
    }
  }
}

ll calculate_sum(){
  ll ans = 1;
  for(auto v: s) ans += v;
  return ans;
}

int main(){
  solve();
  cout << calculate_sum() << '\n';
  return 0;
}