Problem 004

[Genemos]

True enough, an anagram is a palindromic word?

EDIT: Ahh, recalled now, ty.

[hk]

http://en.wikipedia.org/wiki/Anagram
http://en.wikipedia.org/wiki/Palindrome
In a palindrome the word or number reads the same from left to right as from right to left.

[Shreyeder]

This is my code for problem 4. However, with all the answers my output gives me, the THIRD LAST ONE is the accepted solution. Please help me out. I am posting the code in JAVA. (My last 2 answers not being accepted are XXXX and XXXX)

class PE4
{
public void main()
{

snip

System.out.println("answer is the 3rd last option. Why?");
}
}

[thundre]

Wrong forum. But...

The reason those other numbers aren't correct is that the question asks for the largest palindrome, not the last one you happen to find.

[rayfil]

@ Shreyeder

First, we understand you are new to this forum. You must realize that this is an open forum open to all members, who may not have yet solved some of the problems. You must thus be careful about what you post.

Secondly, any question related to published problems must be posted in an existing thread (if it does exist). Problem numbers below 100 are padded with leading 0's to make all of them a 3-digit number. Searching for the relevant thread and reading the existing posts can often answer your question. And, those threads are NOT for posting code nor results. Read the big red sign before posting.

Welcome to Project Euler and to this forum.

[Shreyeder]

My apologies. Thanks a lot for the clarification and to look up forums for particular problems (Y)

[johanafm]

I could use a little help to find out where I go wrong…

The parts I'm working with are

• highestPalindrome - returns the next lower palindrom from input
• factorize - returns the biggest factor below 1000 of its input

I use 998 001 (999 * 999) as starting point for finding the next palindrome.

The first 3 (rejected) palindromes I find, alongside their respective factorizations, are

• 997799 - 11, 90709
• 996699 - 33, 30203
• 995599 - 319, 3121

And the incorrect solution found by these means, after testing 247 palindromes for possible factorizations, is
749947 - 869, 863

Any suggestions are welcome. I'm trying to avoid spoilers, but please let me know if I need to post more information.

[hk]

I think you are new here but topics in this forum are named Problem xxx. For this problem that is Problem 004.
Further you're not supposed to make a new topic for a problem if there already exists one.
Perhaps you can find your answer in the pages above.

[johanafm]

Sorry about that and thank you for moving my post.

Since posting I've come to realize that my error was with finding the correct factors for each palindrome. Then I realized that instead of "building" the factors by prime factorization, it would be better to start looking for divisors from the other end.

[sohamc]

Just started with Project Euler and don't quite know if this question has asked before in the forum.

http://projecteuler.net/problem=4

Can anyone explain to me what does the statement mean by "largest palindrome made from the product of two 2-digit numbers"...I mean that is supposed to be 9779(11*77...two 2-digit numbers)...then how is it 9009??

Thanks in advance!!

[Marcus_Andrews]

11 * 77 = 847, not 9779

[yth]

Is there are a more efficient solution to this problem than O(n^2)?

[Svartskägg]

Is there are a more efficient solution to this problem than O(n^2)?

I think mine is O(n log n).

[thundre]

Is there are a more efficient solution to this problem than O(n^2)?

I think all general algorithms will take O(n²), but the clever ones have a much lower constant.

You could go crazy optimizing. For example, 10 is an even base. If you assume the first digit of the answer is 9, the last digit must also be 9. Then you can infer it's either xx1 * xx9 or xx3 * xx3. However, if it turns out there isn't an answer beginning with 9, you might have just wasted a chunk of time...

[yth]

I think someone posted their ran speed for solving this in a few ms range. That's 50+ times faster than my code. I already restrict my code to only check the highest 50 numbers or so. That's why I was wondering if there is something more efficient.

[Svartskägg]

I think someone posted their ran speed for solving this in a few ms range. That's 50+ times faster than my code.

That's slow. My code takes 10 μs and checks 500 numbers.

Which programming language are you using?

[Falke88]

Its not about how you calculate the products - in which order. Just be sure to return the highest palindrom number "at the end".

[nanogyth]

If you assume the first digit of the answer is 9, the last digit must also be 9. Then you can infer it's either xx1 * xx9 or xx3 * xx3.

or xx7 * xx7

[thundre]

If you assume the first digit of the answer is 9, the last digit must also be 9. Then you can infer it's either xx1 * xx9 or xx3 * xx3.

or xx7 * xx7

Of course.

(Doh!)

[youssef]

Hi everybody,
so i just started learnig python (i 've never learned any languages before) a couple days ago, and i'm stuck on problem 004
so I was wandering if you gus could help me figuring out what's wrong with my code,
here it is:(btw i tried making a program thatt would work not only for three digits numbers.. maybe I souldn't have?, i know it's certainly not optimal and a little bit far fetched)

(btw english is not my native language so i'm sorry for any mistake you'll find)

first i have tried creating a function that gives me the inverse of a given list, this one works perfectly I think, the problemen is with the second one:

-------------------------------------------------------------------------------------------------------------------
<code removed by moderator: see the big red banner on top>
--------------------------------------------------------------------------------------------------------------------------------


the problem is that it doesn't work at all for example :
palindrome(1) gives me
['1']
['2']
['3']
['4']
['5']
['6']
['7']
['8']
['9']
['0', '1'] (now this is the inverse list of 10)
['2', '1'] (of 12)
['4', '1']
['6', '1']
['8', '1']
['1', '2'] (of 21 which is the next j*3 bigger than any j*2 that is 18...)
['4', '2']
['7', '2']
['8', '2']
['2', '3']
['6', '3']
['0', '4']
['5', '4']
['8', '4']
['4', '5']
['6', '5']
['3', '6']
['4', '6']
['2', '7']


Please help me if you can .. why my code is wrong, or just any advice you'd have for me,

Ps i don't know if i can post any fragment of code here, but since it doesn't work i tought it would be okay
i didn't manage to hide it