weird for-loop ( interesting )

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
tang3li2
Forum Newbie
Posts: 7
Joined: Sun Mar 20, 2011 10:36 am

weird for-loop ( interesting )

Post 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 :D
Last edited by Benjamin on Fri Oct 21, 2011 8:08 am, edited 1 time in total.
Reason: Added [syntax=php|sql|css|javascript] and/or [text] tags.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: weird for-loop ( interesting )

Post by VladSun »

It will be a way easier if you give us the problem description :)
There are 10 types of people in this world, those who understand binary and those who don't
tang3li2
Forum Newbie
Posts: 7
Joined: Sun Mar 20, 2011 10:36 am

Re: weird for-loop ( interesting )

Post 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
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Re: weird for-loop ( interesting )

Post 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.
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Re: weird for-loop ( interesting )

Post 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 ;)
tang3li2
Forum Newbie
Posts: 7
Joined: Sun Mar 20, 2011 10:36 am

Re: weird for-loop ( interesting )

Post 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 :D, have a great day :D
tang3li2
Forum Newbie
Posts: 7
Joined: Sun Mar 20, 2011 10:36 am

Re: weird for-loop ( interesting )

Post 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 :D , thank you, thank you so much :D
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Re: weird for-loop ( interesting )

Post 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
Post Reply