I wanted to find a cool way to traverse palindromes only but I got stuck in the numbers so this is all I came up with. I wish I knew maths. I don’t even know what this relation is called when you have a pair of iterators and you increment one by 10^i and the other by 10^-i. And yes it would’ve been simpler to just traverse 999 down to 100 and then mirror it every iteration with string operations.
Thought it would be kind of fun to visualize the “shave”. Using Python’s Pillow, I made images that represent the values that were iterated in some of the algorithms above. Really demonstrates how effective that %11 trick is!
I didn’t try to translate the JS solutions to Python, but anyone feel free to mess with the script:
img = Image.new("RGB", (1000, 1000))
px = img.load()
# fill white
for i in range(1000):
for j in range(1000):
px[i, j] = (256, 256, 256)
def isPalindrome(i, j):
s = str(i * j)
return s == s[::-1]
def addPixel(i, j):
val = i * j * 256 // 1000000
if isPalindrome(i, j):
px[i, j] = (0, 20, 128)
else:
px[i, j] = (256-val//2, val//2+128, 256)
# Your algorithm here
# Call addPixel(i, j) in the innermost loop
img.save('image_name.png', 'png')
Oh and I’ll add my own- after doing this I thought of my own way to cut down on loops. I wonder if anyone can guess what’s going on from the picture alone?
max_pal = 0
for i in range(999, 0, -1):
if i * 999 < max_pal:
break
for j in range(999, i - 1, -1):
addPixel(i, j)
if i * j < max_pal:
break
if isPalindrome(i, j):
max_pal = i * j
print("max", max_pal)
On mobile discords symbol to expand the image nearly covers the entire key part of the image and of the three together above I had to full screen the third one to see it wasn’t all white.
So? - but not solely from the picture
So are you looping backwards in a triangle because multiplication is commutative, and because you only care about the biggest one, which will probably be from the biggest numbers anyway.
So find a palindrome, make that the new biggest and then if the product of the two numbers in the loop drops below the current biggest palindrome, stop since both indexes are decreasing anyway for the inner loop.
Then if even multiplying by 999 drops you below the biggest one found then also stop the outer loop again because it’s decreasing.
Hmm… so I googled and saw the proof for “All even-digited palindromic number % 11 == 0”, but even then, the solution is not complete, because we’re haven’t proved that the target number is even-digited?
I think in this specific case for 3 digit * 3 digit numbers they’ll have between the digits of 100*100=10000 which is 5 digits and 999*999=998001 which has 6 digits.
If you assume there’s an answer in between 900*900=810,000 which has six digits and 999*999 then you only need one of the six digit checks.
So some of the code that is fast in doing a reverse search or only checks a certain range presumably makes an assumption like that, unless there’s some known easy example that guarantee an answer in a particular range
Or well you can try it and if it works it works and if it doesn’t you modify it
I was trying to come with examples that were 1001*x where x is a three digit number such that 7*x<1000, since 1001=7*143, it it shifts and copies a three digit number into six digit one
Eg a number like 101*7*143=101,101 Which is also 101*1001=101*1000 +101=101000+101.
So there is a six digit one at least eg 707*143 above. So then you can use the six digit checks if you search above this
Yes I believe the algorithm in question relies on the assumption that the solution has exactly 6 digits.
The residue when dividing by eleven can be computed by repeatedly calculating the sum of digits with alternating sign until the result lies between -10 and +10. For example 5050567 → 7 - 6 + 5 - 0 + 5 - 0 + 5 = 16 → 5
For any palindrome with even number of digits the alternating sum is zero. However this is just a necessary condition, not a sufficient one, hence the condition is also applied to certain digit-sub-sequences (e.g. check if ABCDEF is divisible by 11, then check BCDE and then CD)
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Easy, no? Should we pretty much skip this?
Looks like you just give it the equation 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19, without any coding even being involved. That’s 232,792,560.
But I suppose there’s fun in making a function to work on any number. Even in that case, I wouldn’t be doing any big modulus loops: rather, I’d still just have the code produce a list of key factors like this and multiply them.
Could always code a solution that takes arbitrary N instead of fixed 20…
Also I think I’ve seen something called project euler + with wider limits around if any of these are too easy. Idk if that’s just a hackerrank.com thing or what though.
from functools import reduce;
def is_prime(n):
if n < 2: return False;
elif n % 2 == 0:
if n == 2: return True;
else: return False;
for i in range(3, n, 2):
if n % i == 0: return False;
return True;
def max_exponents_under(n):
maxPrimeExpList = [];
primeExpList = [];
primeExp = 0;
expt = 2;
if n < 2:
return [n];
for i in range(2, n + 1, 1):
# Record exponents of new primes
if is_prime(i) and (not (i in primeExpList)):
primeExp = i;
expt = 2;
while primeExp <= n:
primeExpList.append(primeExp);
primeExp = i ** expt;
expt += 1;
maxPrimeExpList.append(i ** (expt - 2));
return maxPrimeExpList;
def smallest_multiple_of_numbers_below(n):
numsToMultiply = max_exponents_under(n);
if len(numsToMultiply) >= 2:
return reduce(lambda x, y: x * y, max_exponents_under(n));
else: return numsToMultiply[0];
print(smallest_multiple_of_numbers_below(20));
