Nice no-computers way to find limerick primes?

Question

A limerick number is a 5-digit number whose digits are in the form of a limerick rhyme scheme: $aabba$. How many limerick primes (limerick numbers which are also prime) are there?

The answer is

eight, as a guy on the internet

found using a computer program.

Is there an easy "aha" way to do this without using a computer? Or at least, what is the quickest (least calculation) method to find limerick primes by hand? Obviously there's a relatively short and finite list of all limerick numbers, but how many of these can we winnow out as "obviously composite" before we start having to hunt for big factors?

Answer 1

I'd start with the last digit first:

It can't be 2,4,5,6,8. That helps a lot as it also limits our first two numbers.

Now we're looking at this subset of numbers:

11001, 11221, 11331, 11441, 11551, 11661, 11771, 11881, 11991, 33003, 33113, 33223, 33443, 33553, 33663, 33773, 33883, 33993, 77007, 77117, 77227, 77337, 77447, 77557, 77667, 77887, 77997, 99009, 99119, 99229, 99339, 99449, 99559, 99669, 99779, 99889

With a little trick/some summations we can eliminate:

11001, 11331, 11661, 11991, 33003, 33663, 33993, 77007, 77337, 77667, 77997, 99009, 99339, 99669 - sum of digits is divisible by 3, so number is also divisible by 3

That leaves us with these 22 possibilities:

11221, 11441, 11551, 11771, 11881, 33113, 33223, 33443, 33553, 33773, 33883, 77117, 77227, 77447, 77557, 77887, 99119, 99229, 99449, 99559, 99779, 99889

Then we can eliminate a couple more with another division rule (thanks @IronEagle)

"if (110*b - 10*a ) is divisible by 7", then the number is also. So we can eliminate "11221 (210), and 99449 (350)"

To get the final 8 from these 20 we just...

Copy and paste from the link! haha this is where I'm stuck. I'd have to start hunting factors. Hopefully someone can extrapolate on this and/or do better.

Note: I assumed a!=b for it to be a limerick. I've seen variations of this interpretation in other answers. Either way, all cases of a==b are composite, 2-9 obviously(x*11111), and 11111 is divisible by 41(less obviously, credit @issacg).

Answer 2

Obviously a is one of {1,3,7,9} and a,b are coprime. Also, b can't be a multiple of 3 regardless (else our number is a multiple of 3). That leaves 23 possibilities (4 for a, 6 for b, but we can't have a=b=7), or 22 if you don't count 11111 as "limerick".

The only other trick I see is that 1001 = 7x11x13; so mod 1001, aabba = 11b-a. Clearly that isn't going to be a multiple of 11 in any of these cases, but it's a multiple of 7 for 11221 (21) and 99449 (35) and a multiple of 13 for 33553 (52) and 99229 (13). I'm not sure that the arithmetic saved by spotting these is more work than it takes to spot them, but this brings us down to 19 possibilities. (18 if you don't count 11111 as "limerick". That one happens to be composite but it's not terribly obvious.)

Of these, almost half are actually prime, and I don't see any obvious patterns in the composite ones. I suspect we're out of usefully-spottable tricks. You might happen to spot that 11881 = 10000 + 1800 + 81 = 109^2, or that 99889 = 90900-100 + 9090-10 + 9 and that 90900, 9090, and -100-10+9 are all multiples of 101, but I don't see any reason why you should. (I didn't; I looked at the factorizations my computer gave me and thought "there's probably a neat way to spot those if you happen to think of it".)

Answer 3

As others (ex: Gareth McCaughan) have mentioned, by looking at divisibility by primes up to 13 we can narrow the list down to 19 possibilities:

11111, 11441, 11551, 11771, 11881, 33113, 33223, 33443, 33773, 33883, 77117, 77227, 77447, 77557, 77887, 99119, 99559, 99779, 99889.

Now, we'd like to test for divisibility by higher primes. To do so, we can make use of the fact that limerick numbers are all of the form a*11001 + b*110. We start by computing 11001 mod p and 110 mod p for the prime p we're testing. Let's do this for p=17 as an example.

11001 mod 17 = 2, 110 mod 17 = 8.

Now, we simply need to solve for 2a+8b = 0 mod 17, where a is 1, 3, 7 or 9 and 0 < b < 10. Since 17 is a prime, there will be at most one b for each a. This gives the solutions (a, b) = (1, 4), (9, 2).

This tells us that 11441 and 99229 are divisible by 17, out of our remaining candidates. We already knew 99229 was divisible by 13, but 11441 is freshly eliminated. Now we're down to 18 candidate limerick primes!

By this method, I calculated that 19 divides no new limerick numbers. 23 divides 99889. 29 divides 77227, 31 divides 33883, 37 divides nothing new, and 41 divides 11111.

Obviously, we could keep going like this, though the hit rate will slow down as the prime we are testing increases. There are 14 candidates remaining at this point:

11551, 11771, 11881, 33113, 33223, 33443, 33773, 77117, 77447, 77557, 77887, 99119, 99559, 99779.

Answer 4

"So, you got what I said about limerick numbers, right? Well, the thing is, some of them are probably primes. You know what, I'm going to pay for your next beer if you manage to guess how many. You have one minute!"

The gears in Brian's head started grinding.

One minute? I guess I could pull out my phone and look for "limerick primes" or something. But has anyone really cared about those numbers before? Worst case, I'm just going to end up with questionable poetry and no beer.

Old-school it is then. Let's see, how many candidates are there?

The first number can't be a 0, and the second one can't be equal to the first, so 9*9 = 81 candidates.

But how many of those are primes? Clearly not all. Let's see, there's something to guesstimate how likely a random number is to be a prime:

The prime number theorem! So each of those have a probability of 1/ln(N) of being prime

But wait! That's some logarithm stuff, I don't have enough time for this! Nah, wait, I got this:

3*3 is less than 10, so since $e$ < 3, there are a bit more than two powers of $e$ in each power of ten. Since these numbers are between magnitude 4 and 5, the logarithm should be about 10.

Multiplying those together, we get:

$81 \cdot 1/10 \approx 8$

Looking at the clock, Brian noticed there was still more than 20 seconds to go. Could he do better?

Let's go back to the number of candidates again.

The first number can clearly not be 0,2,4,6,8 or 5, so only 4 possibilities. The second one can be any other, so 4 * 9 = 36 candidates.

But that messes up the nice prime number density thing. Luckily, it doesn't loose generality.

Remove all those divisible by 2, and then a fifth of the rest, we are left with 40% of numbers.

So then we can replace:

1/10 with 1/4.

Using the new number of candidates and the new heuristic, he got:

$36 \cdot 1/4 \approx 9$

At this point, there wasn't any time left to sum the digits to check divisibility by 3 or anything like that, so that was his final guess.

Unfortunately for Brian, playing dice with deterministic numbers doesn't always play out in your favour. In this case he was close, but the extra little clever manoeuvrer didn't work out.

No free beer for Brian today, but it was worth a shot(pint?).

Good friends as they were, they got another round anyway and continued enjoying the Friday afternoon.

Answer 5

The number of candidates is very limited.

If "a" is even or 5, the resulting number is obviously a composite.

If "b" is a multiple of 3, the sum of digits is a multiple of 3, therefore the resulting number is a multiple of 3.

If "b" is "a", the resulting number is obviously a multiple of "a".

So you are left with a list of 23 candidates:

• 11bb1 with b = 1, 2, 4, 5, 7 or 8
• 33bb3 with b = 1, 2, 4, 5, 7 or 8
• 77bb7 with b = 1, 2, 4, 5 or 8
• 99bb9 with b = 1, 2, 4, 5, 7 or 8