Results 1 to 13 of 13
Like Tree5Thanks
  • 1 Post By ebaines
  • 1 Post By romsek
  • 1 Post By ebaines
  • 1 Post By romsek
  • 1 Post By SlipEternal

Math Help - Problem #11: Prime Numbers

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Problem #11: Prime Numbers

    What primes p exist such that 1/p has a purely periodic decimal expansion with a period of 6?

    (For example, 1/11 = 0.09 \overline{09} has a period of 2.)

    (Source based on a problem by: Sanderson Smith. No peeking!)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,091
    Thanks
    315

    Re: Problem #11: Prime Numbers

    Hmm. 7 is one such prime:

    1/7 = 0.\overline{142857}

    So is 13:

     1/13 = 0.\overline{076923}
    Last edited by ebaines; June 24th 2014 at 08:28 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by ebaines View Post
    Hmm. 7 is one such prime:

    1/7 = 0.\overline{142857}

    So is 13:

     1/13 = 0.\overline{076923}
    Interesting. Are there more?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,459
    Thanks
    948

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by topsquark View Post
    What primes p exist such that 1/p has a purely periodic decimal expansion with a period of 6?

    (For example, 1/11 = 0.09 \overline{09} has a period of 2.)

    (Source based on a problem by: Sanderson Smith. No peeking!)

    -Dan
    if $\dfrac 1 p$ has a repeating cycle of 6 then

    $10^6 \left(\dfrac 1 p\right) - \left(\dfrac 1 p\right) = k, ~~ k \in \mathbb{N}$

    $999999 = k p$

    So we want the prime factors of 999999 which are 3,7,11,13,37

    I suppose it's an open question as to whether 1/3 has a period of 6 or a period of 1. It does have a pattern that repeats every 6 digits.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,091
    Thanks
    315

    Re: Problem #11: Prime Numbers

    Thinking about these repeating periods for 1/N .... It's pretty easy to show that the maximum period value for 1/N is N-1 (for example 1/7 has a period of 6, and 1/17 has a period of 16). But of course for many values of N the period is smaller than that - for example 1/11 has a period of 2 (0.90909..) and 1/13 has a period of 6. In considering 1/N for all primes up to 100 I find that the period of 1/N is equal to (N-1)/k, where k is some positive integer that divides N-1. I had not realized that the period is restricted like this. For example, given a prime such as 103 the only possible values for its period are: 1, 2, 3, 6, 17, 34, 51, and 102. As it turns out, the period of 1/103 is actually 34, so k=3. The value for k doesn't seem to follow a pattern:

    Prime, Period, k
    3, 1, 2
    7, 6, 1
    11, 2, 5
    13, 6, 2
    17, 16, 1
    19, 18, 1
    23, 22, 1
    29, 28, 1
    31, 15, 2
    37, 3, 12
    41, 5, 8
    43, 21, 2
    47, 46, 1
    53, 13, 4
    59, 58, 1
    61, 60, 1
    67, 33, 2
    71, 35, 2
    73, 8, 9
    79, 13, 6
    83, 41, 2
    89, 44, 2
    97, 96, 1
    101, 4, 25
    103, 34, 3

    So I'm wondering - is there a way to determine the value of k and hence the period without actually having to do the long division of 1/N?
    Last edited by ebaines; June 24th 2014 at 12:00 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,459
    Thanks
    948

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by ebaines View Post
    Thinking about these repeating periods for 1/N .... It's pretty easy to show that the maximum period value for 1/N is N-1 (for example 1/7 has a period of 6, and 1/17 has a period of 16). But of course for many values of N the period is smaller than that - for example 1/11 has a period of 2 (0.90909..) and 1/13 has a period of 6. In considering 1/N for all primes up to 100 I find that the period of 1/N is equal to (N-1)/k, where k is some positive integer that divides N-1. I had not realized that the period is restricted like this. For example, given a prime such as 103 the only possible values for its period are: 1, 2, 3, 6, 17, 34, 51, and 102. As it turns out, the period of 1/103 is actually 34, so k=3. The value for k doesn't seem to follow a pattern:

    So I'm wondering - is there a way to determine the value of k and hence the period without actually having to do the long division of 1/N?
    they have period $n$ where $n$ is the smallest of $10^n-1$ that p divides evenly
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,091
    Thanks
    315

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by romsek View Post
    they have period $n$ where $n$ is the smallest of $10^n-1$ that p divides evenly
    Right, but I challenge you to tell me the prime factors of, say, 10^{109}-1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Re: Problem #11: Prime Numbers

    Spoilers guys! Spoilers!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by ebaines View Post
    Right, but I challenge you to tell me the prime factors of, say, 10^{109}-1
    10^{109} - 1 = 3^2 \times 1192679 \times 712767480971213008079 \times 5295275348767234696493 \times 24682974398435543596240839091037821853728210515008  6881669547


    -Dan
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,091
    Thanks
    315

    Re: Problem #11: Prime Numbers

    Very nice! Indeed 1/1192679 has a period of 109. My abacus isn't big enough to check the others....
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Re: Problem #11: Prime Numbers

    Quote Originally Posted by ebaines View Post
    Very nice! Indeed 1/1192679 has a period of 109. My abacus isn't big enough to check the others....
    I do so love Mathematica.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,859
    Thanks
    722

    Re: Problem #11: Prime Numbers

    I agree with ebaines' original answer.

    As romsek explained, we are looking for primes p such that p | (10^6-1), however we also want p \not | (10^1-1), p \not | (10^2-1), p \not | (10^3-1).

    So, as romsek found, the prime divisors of 999,999 are 3, 7, 11, 13, and 37. Then, the distinct prime divisors of 9, 99, and 999 are 3, 11, 37. Hence, the only primes for which \dfrac{1}{p} has a strictly periodic decimal expansion with period exactly 6 would be \dfrac{1}{7}\text{ and } \dfrac{1}{13}, as ebaines found.

    In general, let A_k = \{p \in \Bbb{Z} \mid p\text{ is prime and }p\text{ divides }10^k-1\}. Then the set of primes p such that \dfrac{1}{p} has a strictly periodic decimal expansion with period exactly N would be:

    A_N \setminus \bigcup_{n\text{ divides }N, n\neq N} A_n

    In other words, we remove all of the primes whose inverses have periods that are actually less than N.
    Last edited by SlipEternal; June 25th 2014 at 01:19 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,931
    Thanks
    334
    Awards
    1

    Re: Problem #11: Prime Numbers

    This discussion is done very well. Thanks to all who participated.

    This is the point where I post my solution, but you all have pretty much done it for me. Good job.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 26th 2012, 05:09 PM
  2. Replies: 8
    Last Post: May 8th 2010, 08:52 AM
  3. Number theory, prime numbers, interesting problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 21st 2007, 01:23 AM
  4. Prime numbers problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 11th 2007, 11:05 AM
  5. Finding prime numbers - problem w/method
    Posted in the Algebra Forum
    Replies: 20
    Last Post: December 10th 2006, 11:04 AM

Search Tags


/mathhelpforum @mathhelpforum