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

Home > Just Math
Power and Divisibility Puzzle (Posted on 2015-08-12) Difficulty: 3 of 5
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.)
Solution 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 0
1 2 1
2 4 4 *
3 8 9
4 16 16 *
5 15 8
6 13 2
7 9 15
8 1 13
9 2 13
10 4 15
11 8 2
12 16 8
13 15 16
14 13 9
15 9 4
16 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information