n can be written in binary format. You’ve already known how to get the most the significant bit. Then just try the second bit, the third bit … There are O(ln(n)) bits to represent n.
But if there are O(ln(n)) bits to find, and each bit takes O(ln(n)) time, we’re up to O((ln(n))^2), right?
let
First, calculate M1,M2, … Mk and store them in an array. Suppose that 2^k is the most significant bit. To determine the second bit, we need to calculate f(2^k+2^(k-1)).
It takes only one multiplication of two matrix.
2 Likes
Ah, now it finally clicked for me! For some reason I was doing it in the wrong order, starting over from 1, 2, 4 every time instead of just checking whether the next-most significant bit should be set or not.
Then I think I understand the whole O(log n)-solution now, very nice. Thanks for taking the time to explain.
1 Like
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
I have a theory that at least one of the two largest factors of a palindrome is also a palindrome.
Optimisation thought
If so, we only need to check products with at least one palindromic factor.
Actually, are even both factors palindromes?
90109=251*359 and both those are it’s prime factors
4 Likes
Hmm seems like 525 has 25 and 21 so I’m not sure how far that gets us
1 Like
But anyway this seems like the definition of premature optimization heh. Iterating over 900 (or even 900x900) numbers doesn’t take long
1 Like
True. But trying to shave is fun.
1 Like
abccba % 11 = 0
1 Like
I think this works (it didn’t). Where do y’all go to check your answers?
What do you mean? Are you not entering your answers into the website? It tells you if you got it right.
EDIT: note that you have to make an account first
3 Likes
There we go.
Indices are, I think, the Python feature I like best.
Python
def palindrome_products(smallestFactor, largestFactor):
palindromes = [];
product = "0";
for a in range(largestFactor, smallestFactor + 1, -1):
for b in range(largestFactor - (largestFactor - a), smallestFactor + 1, -1):
product = str(a * b);
if product == product[::-1]: palindromes.append(int(product));
return palindromes;
print(max(palindrome_products(100, 999)));
Python
m = 0
for i in range(900, 1000):
for j in range(902, 1000, 11):
x = i * j
if x // 10 % 10000 % 11 == 0 and x // 100 % 100 % 11 == 0:
m = max(m, x)
print(m)
3 Likes
Remember to spoiler your solution.
I tried this one in python also, but just a simple double loop.
python
def is_palindrome(x):
value = False;
rev_digits = [];
while (x>0):
rev_digits.append(x % 10);
x = x // 10;
digits = rev_digits.copy();
digits.reverse()
if (digits==rev_digits):
value = True;
return value;
def main():
largest_palindrome = 0;
test_product = 0;
for j in range(100,1000):
for k in range(100,1000):
test_product = j*k;
if is_palindrome(test_product) and (test_product > largest_palindrome):
largest_palindrome = test_product
return largest_palindrome;
x=main();
print(x);
2 Likes
trying to understand :)
So assuming the biggest one probably exists by multiplying things bigger than 900.
If the number is 6 digits long then:
A number a5 a4 a3 a2 a1 a0 could be written like
x = a5 * 10^5 + a4 * 10^4 + a3 * 10^3 + a2 * 10^2 + a1 * 10 + a0
x//10 = a5 * 10^4 + a4 * 10^3 + a3 * 10^2 + a2 * 10 + a1
x//10 %10000 = a4 * 10^3 + a3 * 10^2 + a2 * 10 + a1
x//10 %10000 %11 ≡ -a4 + a3 - a2 + a1
x // 100 % 100 % 11 ≡ -a3 + a2
So the check is showing that a3=a2, a1=a4. What guarantees a5=a0 the first and last digits the same?
I know I haven’t used the stepping in 11’s bit, so maybe it’s in that.
Summary
j % 11 == 0
1 Like
Brilliant, thanks for sharing 
It’s a nice one