11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can we use a computer to create a list of all limerick numbers, prime/composite agnostic, to start from? Or do you want real thinking ;) $\endgroup$ – TCooper Feb 20 at 22:24
  • 1
    $\begingroup$ Before there were computers, people made books of lists of primes: science.sciencemag.org/content/40/1041/855 That'd probably be the way to go, if computers didn't exist. $\endgroup$ – isaacg Feb 20 at 23:36
  • $\begingroup$ I guess these would be a subset of "Full House Primes", which would include all primes containing 2 of one digit and 3 of another in any order. (I tried to find out if anyone has enumerated these, but it's not easy to search for that term without getting swamped with false results for the TV show on Amazon Prime...) $\endgroup$ – Darrel Hoffman Feb 21 at 19:54
  • 2
    $\begingroup$ I don’t come to this site very often but when I do, I’m always amazed by the utter brilliance of the individuals here... $\endgroup$ – dalearn Feb 21 at 21:25
11
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ You can also determine if a candidate is divisible by seven: The Pohlman-Mass method (check Wikipedia) for this particular form means that if (110*b - 10*a ) is divisible by 7, then the whole number is divisible by seven. This knocks out 11221 (210), and 99449 (350). $\endgroup$ – IronEagle Feb 20 at 23:33
  • 3
    $\begingroup$ I would include that "0" for b is removed by the "divisible by 3" section. $\endgroup$ – IronEagle Feb 20 at 23:45
  • 1
    $\begingroup$ It looks like you accidentally eliminated 33223 as a multiple of 3 $\endgroup$ – isaacg Feb 21 at 0:25
  • $\begingroup$ You mean 13 doesn't divide by 3?! (Thanks, updating now) $\endgroup$ – TCooper Feb 21 at 0:39
25
$\begingroup$

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".)

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ If whoever gave me a downvote for this would like to explain why, then I will be happy to improve my answer if I can. $\endgroup$ – Gareth McCaughan Feb 21 at 16:18
  • 2
    $\begingroup$ Why is it obvious that a and b are coprime? $\endgroup$ – BlueRaja - Danny Pflughoeft Feb 21 at 20:04
  • 1
    $\begingroup$ Because anything that divides both a and b also divides aabba. $\endgroup$ – Gareth McCaughan Feb 21 at 20:20
  • 4
    $\begingroup$ Maybe my comment above isn't clear enough. Suppose d divides a, and specifically suppose dx=a. Then d times xx00x is aa00a. Suppose d divides b, and specifically suppose dy=b. Then d times yy0 is bb0. Adding these up, d times xxyyx is aabba, so aabba is not prime. As you say, the only cases that can actually happen have either a=b or both being multiples of 3, but if you asked a similar question in base 36 or something the same general principle would hold. $\endgroup$ – Gareth McCaughan Feb 21 at 20:33
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
5
$\begingroup$

"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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ It's easy to guess that one of your main sites is Worldbuilding :-) $\endgroup$ – Rand al'Thor Feb 21 at 15:16
  • $\begingroup$ @Randal'Thor Haven't been there since 2016 :' $\endgroup$ – SE - stop firing the good guys Feb 21 at 15:18
  • $\begingroup$ @Randal'Thor This is clearly influenced by Brian Brushwood and Scam School. And that's awesome. $\endgroup$ – LeppyR64 Feb 23 at 21:30
4
$\begingroup$

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
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ How did you rule out 11111? Just because 11111 is a multiple of 1 isn't a problem. Also, 77117 should be allowed, not 77777 $\endgroup$ – isaacg Feb 20 at 23:18
  • $\begingroup$ Good catch. 11111 should be there as you said. 77117 is a copy-paste problem. Fixing this, thank you. $\endgroup$ – xhienne Feb 20 at 23:20
  • 3
    $\begingroup$ 11111 shouldn’t be there because b != a, no? $\endgroup$ – El-Guest Feb 21 at 3:49
  • 1
    $\begingroup$ No, but I’m saying that a limerick is of the poetic form AABBA, where A doesn’t rhyme with B. Thus, the bounds for this puzzle (I believe) are to find prime numbers aabba where a != b. $\endgroup$ – El-Guest Feb 21 at 22:51
  • 2
    $\begingroup$ For the record, yes he does... he says in that website that a limerick prime is any prime of the form AABBA where A is an odd number and B is not equal to A. $\endgroup$ – El-Guest Feb 22 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.