835  Square of Primes
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
835  Square of Primes
I have tried this problem, but the time limit is really hard. I build prefix trees for all possible sums and build the square with backtracking. I used the following rule:
First create a row, then seek a prime in the tree which begins with inserted values and create a column and so on. For example for the sample input I first create a row with a prime beginning with 1, then I create a column beginning with 1, then (after backtracking) I create a row beginning with 14, then a row beginning with 14...
My program solves the sample input quickly, but I tried also the input
23
1
and my program runs 30 seconds and creates 88 squares.
Does anyone know a better approach to this problem?
First create a row, then seek a prime in the tree which begins with inserted values and create a column and so on. For example for the sample input I first create a row with a prime beginning with 1, then I create a column beginning with 1, then (after backtracking) I create a row beginning with 14, then a row beginning with 14...
My program solves the sample input quickly, but I tried also the input
23
1
and my program runs 30 seconds and creates 88 squares.
Does anyone know a better approach to this problem?
some preliminary observations
I haven't solved it yet, but made some preliminary observations:
 all digits in the last column and last row should be odd; there are only 608 5digit primes between 10000 and 99999 having all odd digits, out of a total of 8363; only considering these in the last two iterationsteps can bring down executiontimes considerably.
 the sum off the digits should be odd because of that. This roughly halves the number of precalculations (depending on your algorithm), and the number of primes that need to be considered in the first iterationsteps.
 you only have to look for squares where the prime in the first row is smaller or equal then/to the prime in the first column. The mirror from the upperleft/lowerrightdiagonal is another solution (or the same). This roughly halves the number of calculations, but adds a sortingstep. Sorting is relatively cheap, when a maximum of order(100) squares will be found.
I hope this isn't too much of a spoiler (i think it's pretty obvious). If you think so, tell me, and I'll delete the message.
 all digits in the last column and last row should be odd; there are only 608 5digit primes between 10000 and 99999 having all odd digits, out of a total of 8363; only considering these in the last two iterationsteps can bring down executiontimes considerably.
 the sum off the digits should be odd because of that. This roughly halves the number of precalculations (depending on your algorithm), and the number of primes that need to be considered in the first iterationsteps.
 you only have to look for squares where the prime in the first row is smaller or equal then/to the prime in the first column. The mirror from the upperleft/lowerrightdiagonal is another solution (or the same). This roughly halves the number of calculations, but adds a sortingstep. Sorting is relatively cheap, when a maximum of order(100) squares will be found.
I hope this isn't too much of a spoiler (i think it's pretty obvious). If you think so, tell me, and I'll delete the message.

 New poster
 Posts: 10
 Joined: Tue Jun 18, 2002 12:08 pm
 Location: Portugal
 Contact:
Mail me if you want hints
Hi!
My program solves the "23 1" case in 4.23s on my AMD Athlon 700Mhz, giving 88 solutions (as your solution did), using gcc without optimization (if I use the option O3 in the compiler the program takes 1.13s)
"23 3" is even a worst case (152 solutions) and my program takes 5.77s to do that (1.48s with compiler optimization)
I must confess my first approach was similar to yours, using the notion of prefix, and I needed some hints (this program has been studied by some people) to make an accpetable solution.
Imagine input "13 1". Then this (the first square) will be one solution:
Note that the problem states that "Both diagonals are read from left to right.", so 31423 is one of the diagonals. So, the mirror is not always a valid solution and we must calculate all combinations, right?
As I think this problem is very interesting, I will resist posting stronger hints here. But if you need any hints, just email me!
My program solves the "23 1" case in 4.23s on my AMD Athlon 700Mhz, giving 88 solutions (as your solution did), using gcc without optimization (if I use the option O3 in the compiler the program takes 1.13s)
"23 3" is even a worst case (152 solutions) and my program takes 5.77s to do that (1.48s with compiler optimization)
I must confess my first approach was similar to yours, using the notion of prefix, and I needed some hints (this program has been studied by some people) to make an accpetable solution.
Be careful with that!!!xenon wrote: you only have to look for squares where the prime in the first row is smaller or equal then/to the prime in the first column. The mirror from the upperleft/lowerrightdiagonal is another solution (or the same). This roughly halves the number of calculations, but adds a sortingstep. Sorting is relatively cheap, when a maximum of order(100) squares will be found.
Imagine input "13 1". Then this (the first square) will be one solution:
Code: Select all
12253 15313
54013 24223
32413 but 20443 is not valid because 31423=7*67*67 and so is not a prime
12433 51133
33331 33331
As I think this problem is very interesting, I will resist posting stronger hints here. But if you need any hints, just email me!
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."
You're absolutely right, WhiteShadow. I didn't notice that on first sight.
Now that I've been coding a little, I discovered that my observations are of little use. They could bring down calculating times, but not enough for a pure brute force attack to finish in time
I'm not through with this problem...
Now that I've been coding a little, I discovered that my observations are of little use. They could bring down calculating times, but not enough for a pure brute force attack to finish in time
I'm not through with this problem...

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Re: Mail me if you want hints
Hmm, that sounds like if there's some mathematical insight behind it... My solution is just a brute force one, but it's still the fastest one so far (I need about a second for each of the cases 23/1 and 23/3, and on the judge it took about 3 seconds).WhiteShadow wrote: I must confess my first approach was similar to yours, using the notion of prefix, and I needed some hints (this program has been studied by some people) to make an accpetable solution.
I just fooled around with my dummy account a bit and got down to 2.5 seconds...
Yes, please. Now that I have one solution, I'd like to know more about the problem. Could you mail me what you got to pochmann@gmx.de? Thanks...WhiteShadow wrote: As I think this problem is very interesting, I will resist posting stronger hints here. But if you need any hints, just email me!

 New poster
 Posts: 10
 Joined: Tue Jun 18, 2002 12:08 pm
 Location: Portugal
 Contact:
Well, you made me wanna look at the problem again, to optimize a little bit more, and now my solution is again the first one (it took 2.15 s on UVA judge). If you wanna exchange ideas, or just want to know what I did, mail me (pribeiro@dcc.online.pt)
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
So how long would your nonprecalced version run on the judge? Btw, please mark precalc solutions with a "precalc" comment, so that others don't waste time to search for the superior algorithm that doesn't exist. Well, I have to admit that I've just made up this rule for me (never thought about it before) and I'll follow it in the future.
My first version (which was used for precalcing) was very slow, but now i have made an optimized algo (to show that i can optimize too ).
Created a new dummy acount for the same purpose as you. As Locutus i've made it in 1.180 sec.
Next time i will indicate the precalced solution, but for this problem i couldn't reach 0.000 sec, so no modification possible.
Created a new dummy acount for the same purpose as you. As Locutus i've made it in 1.180 sec.
Next time i will indicate the precalced solution, but for this problem i couldn't reach 0.000 sec, so no modification possible.

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
WA  output format??
I'm getting frustrated with this one...
I have it working well on my PC  solves 23,3 in about 4s.
It generates 88 solutions for 23,1 and 152 for 23,3 which agrees with earlier posts. The output seems correct upon inspection.
I was unsure about "The solutions must be in ascending order"  does that mean order by first row, then first column or by first row then second row? I tried both ways (my program generates by the first way but I suspect what is wanted is the second).
"The outputs of two consecutive cases will be separated by a blank line. "
So that is a second blank line after the last solution right?
It works fine for multiple inputs...does it matter if the program reads all input at the beginning or reads after outputting each set?
I've tried a bunch of formats and always WA. Does anyone want me to email my output for 23,3 (or other set) for checking?
Thanks,
Mark (msmammel@starpower.net)
I have it working well on my PC  solves 23,3 in about 4s.
It generates 88 solutions for 23,1 and 152 for 23,3 which agrees with earlier posts. The output seems correct upon inspection.
I was unsure about "The solutions must be in ascending order"  does that mean order by first row, then first column or by first row then second row? I tried both ways (my program generates by the first way but I suspect what is wanted is the second).
"The outputs of two consecutive cases will be separated by a blank line. "
So that is a second blank line after the last solution right?
It works fine for multiple inputs...does it matter if the program reads all input at the beginning or reads after outputting each set?
I've tried a bunch of formats and always WA. Does anyone want me to email my output for 23,3 (or other set) for checking?
Thanks,
Mark (msmammel@starpower.net)
OK
Nevermind...
I found my mistake  there was a little error in sorting that only occurred in one input, I finally found it.
Mark
I found my mistake  there was a little error in sorting that only occurred in one input, I finally found it.
Mark