# handy function to check if a number is palindrome
def is_palindrome(i):
return str(i) == str(i)[::-1]
# what's the max?
max_p = 0
# multiply all numbers `i` between 100 and 998, with all between i+1 and 999
for i in xrange(100, 999):
for j in xrange(i+1, 1000):
p = i * j
if is_palindrome(p) and p > max_p:
max_p = p
print max_p
Comments are welcome.
Update: fixed as per Alex comment.
Drop the if, please, just return the condition.
ReplyDeleteif x:
return True
else:
return False
drives me batty. return x already!
@Alex: oh god, you're so damn right! updating
ReplyDeleteWould it be faster to check only the firesst half versus the last half instead of the whole string ?
ReplyDeleteMines basically algorithmicly the same, just with a single list comprehension.
ReplyDeletehttps://bitbucket.org/prologic/euler/src/bc50ae139f3027d22e32f4fdf925abf8153e42a0/4.py?at=default
cheers
James
@Kontre: probably yes, but then you'll have to handle when len is odd (so the central element should either be ignored or included in both the sub-strings)
ReplyDelete@James: yep, same logic, just one note: you're comparing both A*B and B*A which for a long list would take some time
Why do you skip squares? There is no constraint that the numbers have to be different.
ReplyDeleteRather than count up, count down. Find a max palindrome, then you can limit how small a number you need to multiply by. This saves a lot of multiplies.
ReplyDeleteSorry about the lack of indentation, but I can't figure out how to post code.
--
# handy function to check if a number is palindrome
def is_palindrome(i):
return str(i) == str(i)[::-1]
# what's the max?
max_p = 0
min_mult = 99
# start at 999, work your way down
for i in xrange(999, 99, -1):
if max_p != 0:
min_mult = max_p/i
if min_mult > i:
break
for j in xrange(i, min_mult, -1):
p = i * j
if is_palindrome(p) and p > max_p:
max_p = p
break
print max_p
---
I called yours pal0.py, mine pal1.py.
$ time python pal0.py
906609
real 0m0.558s
user 0m0.488s
sys 0m0.031s
J$ time python pal1.py
906609
real 0m0.068s
user 0m0.033s
sys 0m0.023s
$
This comment has been removed by the author.
ReplyDeleteOr you reverse the order: you first find the potential palindromes, then you find if there is a matching product of two 3-digits numbers. As a one-liner:
ReplyDeleteiter(pal for pal in (num for num in xrange(999 * 999, 100 * 100, -1) if str(num) == str(num)[::-1]) if any((i * j == pal) for i in xrange(999, 99, -1) for j in xrange(i, pal / i - 1, -1))).next()
This only works well because Python allows the palindrome enumeration to be written as a generator expression, and act as a co-routine to the outside dividers search criteria.
I will avoid the nitpicks and try to make an interesting suggestion. Palindromes are endian independent, that means that if you take the bytearray and convert to int using little endian or big endian you'll get the same number.
ReplyDeleteIt could be interesting to solve a problem about numbers using it's own properties instead of converting them to strings.
two signifant improvements on sylvain's solution:
ReplyDeleteA)
- 999*999 = 998001, so the biggest possible palindrome is 997799
- incidentally, 231*481 = 111111, so it's a valid candidate
- so the solution is between 111111 and 997799, hence it has 6 digits
- 6 digit palindromes can be generated from numbers from 999 to 100:
999[999], 998[899], 997[799]...
So the outer loop in sylvain's solution can be written this way:
for pal in (int(str(num) + str(num[::-1])) for num in xrange(997,99,-1)):
...
B) less significant improvement: the inner loop can start at math.floor(math.sqrt(pal)) instead of 999
@Rafael Augusto: I'm not sure how you mean to use that property, but note that a base 10 palindrome is not a base 2 palindrome (e.g. 11 (base10) = 1011 (base2))
ReplyDelete@mpomme: Ahahaha... You are absolutely right -- I didn't give enough thoughts about the specific meaning of what is a 6 digits base 10 palindrome; your enumeration is a significant improvement.
ReplyDelete