Project Euler 346 - Strong Repunits

Official link: https://projecteuler.net/problem=346

Thought Process

First we find the Repunit WolframAlpha page, then we can note the following:

  1. 10^12 = "1110100011010100101001010001000000000000" base 2

    • so we need not look for repunits longer than "1111111111111111111111111111111111111111" that is 40 digits

  2. Simply look through strings of length 3 to 40 digits

    • We do not look through strings of length 1, because for every single base "1" is a repunit, so it is trivially true that 1 is a strong repunit

    • We do not look through strings of length 2, because for all n >= 3, n is trivially the repunit "11" in base (n-1). Take 7 for example it is "11" in base 6. This means that if n >= 3 forms a repunit "111", "1111", or larger in a different base, then it is also a strong repunit because it is "11" in base n-1

  3. From WolframAlpha repunits with base b are equal to (b^n - 1)/(b - 1), where n is the length of the base unit

So we iterate through bases till we have a base such that it exceeds our limit of 10^12, add them to a set which contains our special case 1 and returns the sum of the set

Interactive Code

Enter an integer (yourinput)

Code will output the sum of all strong repunits less than yourinput