Re-ID

Created: Jun 25, 2025

Last modified: Jun 26, 2025

TL, DR.

Show challenge description

Commander Lambda has a morale problem: minions with cool IDs like 1 or 42 keep showing off. Her fix is a "completely foolproof scheme": glue every prime number together into one endless string, 2357111317192329…, have each minion pick a number n, and give them the five digits starting at position n as their new ID. Your job is to write the function that does it, for any n from 0 to 10000.

# Get a feel for it first

Before any code, play with this. Drag the slider or type a number, and watch which five digits get picked. The primes they come from are outlined.

New ID for n = 3: 71113

It starts inside 7 and ends inside 13: IDs don't care about cutting primes in half.

Fun detail: try n = 10000. The ID is 02192, so IDs can even start with a zero. Good thing we return a string and not a number!

# Step 1: getting the primes

Every version below needs a list of primes, and the classic way to get one is the Sieve of Eratosthenes. It works like this: write down every number from 2 up to some limit. 2 is prime, so cross out all its multiples. The next number still standing is 3, so cross out its multiples too. Then 5, then 7... Whatever survives is prime.

A small detail in the code: when crossing out the multiples of p, we start at p * p. Anything smaller, like 2p or 3p, was already crossed out by a smaller prime.

def get_primes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    solution = []
    while (p * p <= n):
        if (prime[p]):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, n + 1):
        if prime[p]:
            solution.append(p)
    return solution

The sieve needs a limit, and that turns out to be the interesting part of this problem: how far do we need to go? Each version below answers that question a little better.

# Version 1: build the whole string

The worst case is n = 10000, and we need 5 digits from there, so the string has to be at least 10,005 characters long. If you count digits prime by prime, you get there at 20231. So: sieve up to 20231, join everything, cut out [n:n+5]. Done!

It's simple and always right, which is the best place to start. The downside: every single call builds a 10,000-character string, even if you only asked for n = 0.
Average time: 0.1706 s

def solution(start_index):
    # This magic number is estimated by putting all the prime numbers 
    # concatenated until they have a length greater than 10004, resulting in 
    # the prime number 20231 https://oeis.org/A000040
    return "".join(str(prime) for prime in get_primes(20231))[start_index:start_index+5]

# Version 2: stop when you have five digits

Do we really need the full string? Not really. We can walk through the primes digit by digit, keeping a counter of our position. When the counter enters the window, we keep the digit; as soon as we have five, we return. No giant string anymore, which more than halves the time.
Average time: 0.0775 s

def solution(start_index):
    # This magic number is estimated by putting all the prime numbers 
    # concatenated until they have a length greater than 10004, resulting in 
    # the prime number 20231 https://oeis.org/A000040
    output = ''
    cnt = -1
    for prime in get_primes(20231):
        for char in str(prime):
            cnt += 1
            if start_index <= cnt < start_index + 5:
                output += char
            if len(output) == 5:
                return output
    return output

There's still waste, though: we sieve all the way to 20231 every time. For n = 3 the last prime we need is 13!

# Version 3: guess the limit from n

What if we could estimate, from n alone, how far the sieve has to go? To find out, I named two things:

Then I computed both for every n from 0 to 10000 and plotted last_prime / last_index. The result was almost flat: the ratio stays close to 2 and grows very, very slowly. (That's no coincidence: it comes from how primes thin out as numbers grow, but for this problem the picture is all we need.)

So a first guess would be limit ≈ 2.02 × last_index, following the trend line. But careful: a line through the middle of the points falls below a lot of them, and falling short means missing primes, which means a wrong ID.

The fix is to lift the line until it sits above (almost) every point. The line also has a tiny slope, so tiny we can drop it. With a factor of 2.13, the estimate is big enough in 99.96% of the cases:

Only 4 values still fail: n = 0, 40, 41 and 42. They're all tiny indices, where a single prime more or less is a big deal compared to the index itself. Adding a small safety margin of +3 takes care of them:

Now it works for 100% of the inputs. And since n can only go from 0 to 10000, I could check every single one of them, so this isn't a hopeful guess: it's a verified formula for this problem.

Want to see how tight it is? Try n = 40 or n = 42 below: the estimate lands exactly on the prime we need.

ID 83899. The formula sieves up to 97, and the last prime we need is 97 (a perfect fit!)

Here's the final version. It sieves only what it needs, and on average it's about 4.5× faster than version 1.
Average time: 0.0372 s

import math


def solution(start_index):
    end_index = start_index + 4
    n_primes = int(math.ceil(end_index*2.13+3))
    s_primes = "".join(str(prime) for prime in get_primes(n_primes))
    return s_primes[start_index:end_index+1]

# Wrapping up

Three takeaways from this one. First, start with the brute-force version: it's your safety net, and it tells you what "correct" looks like. Second, look for work you're doing for nothing, like building a string you'll throw away. Third, when the input range is small and fixed, an empirical formula is totally fair game, as long as you test it against every possible input.

# Bonus: is it really foolproof?

Lambda wanted to end the jealousy by handing every minion a fresh ID, but nobody checked whether those IDs were actually unique. They aren't. Try n = 3 in the first demo, then n = 6681: both get 71113. And it gets worse: n = 4, 5300, 5314 and 5408 all share 11131. Four minions, one ID!

If you run through all 10,001 possible inputs and count how often each ID shows up, here's what you get:

That's only 8,870 distinct IDs for 10,001 minions: more than 2,100 of them share theirs with someone else. No ID shows up five times or more.

Some of this was unavoidable. Even if the IDs were five-digit numbers picked completely at random, spreading 10,001 of them over 100,000 possible values leaves collisions: that's the famous birthday paradox, and you'd expect around 9,517 distinct IDs. But the prime string makes things noticeably worse, because its digits are far from evenly spread. Every prime except 2 and 5 ends in 1, 3, 7 or 9, and almost half the primes we use sit between 10000 and 20231, so they start with a 1. The upshot: 1 makes up about 23% of all digits, four times as often as 0. With that many ones floating around, sequences like 11131 or 31111 keep popping up.

For the challenge it doesn't matter: you're asked to compute the ID, not to make it unique. But if you ever have to design real identifiers, the lesson is clear: something that looks random can still repeat itself.