All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Power and Divisibility Puzzle (Posted on 2015-08-12)
Determine the total number of positive integer values of N < 20150 such that:
2N - N2 is divisible by 17

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Analytic solution | Comment 5 of 6 |
This was more complicated than I thought.
Consider the moduli of  2N and N2 mod 17:
`N   2N  N2 0   1   01   2   12   4   4 *3   8   94  16  16 *5  15   86  13   27   9  158   1  139   2  1310  4  1511  8   212 16   813 15  1614 13   915  9   416  1   1 *17      0`

2N and N2 each have cycles of different length.  2N is length 16 whereas N2 is length 17.  So it's really only every 16*17=272 steps that the great-cycle of their difference repeats.

For 2N - N2 to be divisible by 17, their moduli must be equal, which I will refer to as a match up.

The N2 cycle contains every number in the 2N twice plus an extra 0.  As the two cycles overlap, each number in N2 cycle will twice match up with a number from the 2N cycle (except for the 0) so we have 16*2=32 match ups per great-cycle.

20150/272 = 74 + 22/272

32*74=2368 match ups in the 74 full great-cycles.

The 22 extra steps have 3 more match-ups -- those marked by * in the table (the next actually occurs at 21)

Final tally: 2368+3=2371

 Posted by Jer on 2015-08-13 10:38:31

 Search: Search body:
Forums (1)