10837 - A Research Problem

Sedefcho · Post by **Sedefcho** » Thu Apr 21, 2005 2:15 pm

Aaa, domino

!

If my ideas have motivated you to start solving
this problem then .... You owe me some hints

I am kidding of course.

Well, do you also use recursion ?

I can not even fix my program for inputs like 20 and 2000,
not to talk about that huge number you've given me.

Sedefcho · Post by **Sedefcho** » Thu Apr 21, 2005 2:19 pm

Now I made a small change which produces this output:
4328653313 for input=16842752.

Which is not the correct answer.

Any hints from you, domino or from observer
will be appreciated.

sidky · Post by **sidky** » Thu Apr 21, 2005 4:23 pm

Thanks domino. I was really stuck on this problem. Now its AC.

Sedefcho · Post by **Sedefcho** » Thu Apr 21, 2005 4:34 pm

Code: Select all


Domino Wrote: 

Is there any solution for this input 

16842752 
0 

My program works for all test cases posted here, but i still receive Wrong Answer. I believe the above is in the judge's input, but my program says there is no solution for it. Any help would be great!

Domino, what is so special about that number?
Seems now I am in the situation you were in when you
made this post. I cover all test cases posted here
except for this number.

domino · Post by **domino** » Thu Apr 21, 2005 6:24 pm

Well, it seems you figured it out that tests like 20 and 2000 weren't working because you didn't treat the case when the phi_n = p^k*(p-1) (p prime) and the minimal n could have been p^(k+1) (it's not always p^(k+1) as you realised that for 32 it was 51).
So, my test case is like this:

N = 33817088
phi(N) = phi(2^9 * 257^2) = phi(2^9) * phi(257^2) = 2^8 * 257*256 =
= 16842752

When you work backwards from this you do the following:
16842752 = 2^8 * 257*256
min_N_from_PHI_N(257*256) = 257^2 but
min_N_from_PHI_N(2^8) = 257 (not 2^9 = 512)
so, because gcd(257^2, 257) != 1 you do not get the proper result
what should you do? well, i just tried another value for X in phi(X) = 2^8 (i try 257 and see it doesn't work and i try 512 afterwards)
If you need more hints, asks, i owe you!

domino · Post by **domino** » Thu Apr 21, 2005 6:29 pm

Oh, and by the way, how are people solving this in under 0.1s? I have 0.5s runtime after hashing the results with a STL map. Could someone share some hints? (i see Adrian Kuegel for example has a really fast solution)

Sedefcho · Post by **Sedefcho** » Fri Apr 22, 2005 1:53 am

Domino,

First, thank you for the support.
Although the algorithm is apparently not so good
in terms of performance.

Second,

Code: Select all

Well, it seems you figured it out that tests like 20 and 2000 weren't working because you didn't treat the case when the phi_n = p^k*(p-1) (p prime) and the minimal n could have been p^(k+1) (it's not always p^(k+1) as you realised that for 32 it was 51).

The answer is : yes, I realised that.

Third,

16842752 = 2^8 * 257*256
is the answer to my question
"what is so special about this number ? "
Of course your explanations which follow
make it even more clear.

I will try to fully understand them and implement them
somehow

As far as I understand :

let's say you do this

res1 = calc_N_from_PHI_N(J) ;
res2 = calc_N_from_PHI_N(num/J);

1) If res1 and res2 have no common divisor than
we have no problem. In this case we
generate res1*res2 and we put it in the list of
our candidates for N ( whose phi(N)==num ) .

2) If they have common divisor - than what ?!
I think in that case you assume that J has the form
(p^k) * (p-1) and you do this : assign p^(k+1) to res1
( res1 = p^(k+1) )

So ...

I. You actually generate a second candidate for res1
after the first one has failed due to the reason it has
a common divisor with res2 ?! Right ?
And then you put res2 * res1 in the list of your candidates.
( and that is the difference with what I do not - I would simply
reject it as gcd(res1, res2) != 1 )

Is that what you meant ?!

Or ...
II. maybe you check all numbers between
res1 and p^(k+1) in the case when res1 and res2 have
common divisor > 1 ?! I mean you calculate their PHI and you
check if it is equal to J ?!
This option No.II sounds less probable to me.

As you can see I'm slightly stupid so I need some more
explanations

By the way I am not sure "our algorithm" is always correct.
I mean mathematically. It's a sort of a heuristic algorithm.

This explains the fact I have WA. Maybe the judge should
give ACC for programs which generate correct answers
for 90% of the test cases

Observer · Post by **Observer** » Fri Apr 22, 2005 6:14 am

Hi,

Don't have much time to write much on this topic, as I'm busy with my final exam...

So you should see that your program should care more about prime numbers, rather than relatively prime numbers. The reason why the splitting 10 * 1000 doesn't work is that, your old code would certainly try splitting 1000 into 10 * 100, and thus gives 11 * 11 * 101 as an output, which is incorrect.

I think you know how to deal with cases like 20 (= 4 * 5 = 5 * (5-1))... The explanation given by domino is very nice~

domino · Post by **domino** » Fri Apr 22, 2005 8:28 am

Sedefcho wrote: As far as I understand :

let's say you do this

res1 = calc_N_from_PHI_N(J) ;
res2 = calc_N_from_PHI_N(num/J);

1) If res1 and res2 have no common divisor than
we have no problem. In this case we
generate res1*res2 and we put it in the list of
our candidates for N ( whose phi(N)==num ) .

2) If they have common divisor - than what ?!
I think in that case you assume that J has the form
(p^k) * (p-1) and you do this : assign p^(k+1) to res1
( res1 = p^(k+1) )

So ...

I. You actually generate a second candidate for res1
after the first one has failed due to the reason it has
a common divisor with res2 ?! Right ?
And then you put res2 * res1 in the list of your candidates.
( and that is the difference with what I do not - I would simply
reject it as gcd(res1, res2) != 1 )

Is that what you meant ?!

Yes, this is actually what i meant..a second candidate for res1... note that sometimes N/j might fail and you might need a second candidate for res2.. it worked to get ACC although i have no proof

Sedefcho · Post by **Sedefcho** » Fri Apr 22, 2005 3:42 pm

Yes, Domino,

With that "fix" or "patch" ( how should we call it ? )
of our algorithm I also managed to get ACC.

I doubt we can prove this algorithm is always correct
because I doubt it is always correct

Thanks for the help once again.

My runtine though is about 5 secs. Apparently it's not the
best algorithm with respect to performance.

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Apr 22, 2005 6:57 pm

Actually, a fix for your problem with 16842752 is, when you split up, you give as parameter the index of the smallest prime factor that is allowed (only prime factors > than the ones used so far are allowed).
And btw, I use a "brute force" search for N, but just memoize intermediate results, where a state has the from: phi_n, smallest allowed prime.