Finding locker at the gym in O(1)
Written , a 5 minute read
After taking a break for a year or so, I have recently started going to the gym!
(not so) Fun fact
The first time I get to the gym was when in the rented flat our heat was cut out due to some issue with the pipes in the building. We didn't have both warm water and heating in the middle of the winter, so even cold showers were out of the option. That's why going to the gym for the shower was quite a good option and since I was already there I could do some excercise.
To my unfortunate suprise the new gym that I have picked was quite busy, especially in hours that were suitable to me. My old method of picking lockers using powers of two (and powers of two minus one) resulted in situation where all my preffered locker numbers were already taken.
I have to came up with a new plan. Powers were out of the game, since they are quite sparse in the range of the lockers - from 1 to 230. The same goes for Fibonacci/Lucas numbers. Then the moment of wisdom came to me - prime numbers! Compered to the previous method using powers this was major increase of available lockers. But how to quickly determine if the number is prime?
Looking for primes in the wild
I love math but hate and can't count. Even adding two digit number in my head I must do step by step, often out loud. So if I wanted to only use primes my method of prime testing must be suitable for my one brain cell. For the first 3 times at the gym I just looked at the number and used vibes to judge primality and then checked on OEIS during excercise if I was right.
Last time I wasn't vibing with the number so I started to do some quick checks based on primary school divisibilty tests for 2, 3, 5 and making sure that it didn't came up in multiplication table. Note that since we are checking for the primality, we only have to check divisibilty by primes. Later that day I wondered how good those method were in the given lockers range (up to 230).
Since this is quite mathy subject I created Haskell file and started writing some checks. You can find full code here.
Primality tests that even I can do in my head
My main battery of tests is:
- If ends with 0, 2, 4, 5, 6, 8 (divisibilty by 2 and 5)
- or the sum of it's digits is divisible by 3
- or is a two digit number with equal digits (divisibilty by 11)
- or is the square (max 13^2)
then this number is not a prime. Others probably are.
| Method | Count |
|---|---|
| Powers of two (and one less) | 14 |
| Real primes | 50 |
| Looking like primes | 60 |
More then 3 times available lockers! But with a caveat: I may pick a locker that looks prime but isn't - and have this shame on me for the rest of my life. To prevent this I generated list of the fake primes and their prime factors.
| Number | Divisbile by | |||||||
|---|---|---|---|---|---|---|---|---|
| 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | |
| 91 | T | F | T | F | F | F | F | F |
| 119 | T | F | F | T | F | F | F | F |
| 133 | T | F | F | F | T | F | F | F |
| 143 | F | T | T | F | F | F | F | F |
| 161 | T | F | F | F | F | T | F | F |
| 187 | F | T | F | T | F | F | F | F |
| 203 | T | F | F | F | F | F | T | F |
| 209 | F | T | F | F | T | F | F | F |
| 217 | T | F | F | F | F | F | F | T |
| 221 | F | F | T | T | F | F | F | F |
I really would benefit from divisibilty by 7 test or better multiplication skills (by 11 especially).
Confusion matrix and performance metrics
I was curious how this seems from the methods used by AI folk. Let's start with classic, confusion matrix:
| Predicted | |||
|---|---|---|---|
| Positive | Negative | ||
Actual |
Positive | 50 | 0 |
| Negative | 10 | 170 | |
which gives:
- accuraccy: 0.96
- precision: 0.83
- recall: 1.00 (this one was obvious)
Unfortunatelly this is where my education in AI dev ends.
Divisibilty by 7 sucks
I think that learning to calculate divisibilty by 7 in head is harder then remembering extended multiplication table. But I still want to try it to excercise not only my body but also my mind at the gym. Unfortunatelly the rule is complex:
subtract twice the last digit from the number formed by the remaining digits. Continue to do this until a number is obtained for which it is known whether it is divisible by 7.
So for now I would stay with the tests suitable for my braincell and try to remember when it doesn't work. I will try to compute divisibilty by 7, but I often go to the gym after whole day at the university with no brain power left.
Conclusion
Let's pretend that this post has nice structure. What have we learned? That divisibilty rules from primary school are suprisingly effective for primality test, that's for sure. See ya!