Page 1 of 1
weird for-loop ( interesting )
Posted: Thu Oct 20, 2011 2:57 am
by tang3li2
I found this code on a solving problem programming competition.
the last code which is i don't understand, i hope someone can explain it to me briefly, if you don't mind, it will be a great help for me and i will appreciate the help
i already did some scratch code to break the code, but unluckily i came up with nothing, i really needed help on this one..
this is the code
Code: Select all
for($n=0;$v=++$n<765;$i||print"$n
")for($i=6;$n>$v+=1;)
$i-=$n%$v<1&&$n%pow($v,3)+$n%$v*$v;
what i don't understand is the last line
this one:
Code: Select all
$i-=$n%$v<1&&$n%pow($v,3)+$n%$v*$v;
i hope someone can explain it to me briefly, thank you so much in advance

Re: weird for-loop ( interesting )
Posted: Thu Oct 20, 2011 3:33 am
by VladSun
It will be a way easier if you give us the problem description

Re: weird for-loop ( interesting )
Posted: Thu Oct 20, 2011 4:19 am
by tang3li2
ok, sorry for that, the thing is, no INPUT is required, the only thing needs is to print the OUTPUT
DESCRIPTION:
Print the first 100 sphenic numbers in increasing order.
Output:
30
42
66
70
78
102
105
110
114
130
138
154
165
170
174
182
186
190
195
222
230
231
238
246
255
258
266
273
282
285
286
290
310
318
322
345
354
357
366
370
374
385
399
402
406
410
418
426
429
430
434
435
438
442
455
465
470
474
483
494
498
506
518
530
534
555
561
574
582
590
595
598
602
606
609
610
615
618
627
638
642
645
646
651
654
658
663
665
670
678
682
705
710
715
730
741
742
754
759
762
Re: weird for-loop ( interesting )
Posted: Fri Oct 21, 2011 7:47 am
by Mordred
Oh god. The mind that produced that should be ... interesting to look at. From a safe distance of course
There's a minor 'bug' in the code: the +$n%$v*$v; does nothing and can be removed.
It looks for n = a*b*c where a,b,c are different primes.
Look at the problem from another angle: if you have an n = a*b*c and you try to divide n by all numbers between 2 and n-1, how many 'whole' divisions (with no modulo) would you get?
The answer is six:
a, b, c, ab, ac and bc
The only problem you'll have is with numbers which are n=a*a*a*b which also have six:
a, b, aa, ab, aaa, aab
(I don't have proof that there aren't more combinations that also produce exactly six divisors, but for the several I tried it looked correct)
So if we can check if n % a^3 == 0 and throw these away, we're fine.
This is what the code does in a very, very twisted way.
On second thought, the author maybe didn't think of the method himself, because of the mistake with $n%$v*$v, which is always 0. Maybe he meant n%v^2 which is also redundant, since we already checked for n%v^3.
Re: weird for-loop ( interesting )
Posted: Fri Oct 21, 2011 8:13 am
by Mordred
Aha, found him:
http://golf.shinh.org/reveal.rb?Sphenic ... 813804&php
The Python solutions follow the same idea, so at least the idea is not new. The unnecessary +$n%$v*$v seems to be an "invention" of this guy though

Re: weird for-loop ( interesting )
Posted: Sun Oct 23, 2011 6:01 am
by tang3li2
thanks men, i really appreciate your explanation, it really need some critical thinking in here huh =)), thanks a lot, i will study your explanation, thanks a lot

, have a great day

Re: weird for-loop ( interesting )
Posted: Sun Oct 23, 2011 6:04 am
by tang3li2
just one more time,
what do you mean by this???
"if you have an n = a*b*c and you try to divide n by all numbers between 2 and n-1"
can you please give an brief example, thanks a lot

, thank you, thank you so much

Re: weird for-loop ( interesting )
Posted: Sun Oct 23, 2011 2:36 pm
by Mordred
Pick a sphenic number N. Divide N by all number between 2 and N-1. Count how many divide N with no remainder. The count would always be 6 for a sphenic number. If we say that N=a*b*c (by the definition of a sphenic number), the six dividers would be a, b, c, a*b, a*b and b*c