Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Wed Jul 23, 2014 3:25 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 20 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: fractions puzzlePosted: Thu Jul 07, 2011 1:09 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
given the fractions 1/1 1/2 1/3 ... 1/99 1/100 (all in base 10)

Is there a way to intuitively or logically (without using brute force) determine which fraction has the longest repeating sequence? If so, I'd be curious to see this. I have a hunch that it would be a prime number, but have no proof or anything.

-d

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 1:37 pm

Joined: Wed Mar 11, 2009 3:33 pm
Location: Pennsylvania, USA

_________________
NEEDS MORE LUBIX

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 2:08 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
Yes it does, but it's just one 3 repeating. I'm looking for the longest sequence. one 3 repeating would just be a sequence of 1 number. 1/7 is a sequence of six numbers repeated (.142857...)

Obviously numbers like 1/8 wouldn't count since the sequence ends and it's only three numbers (0.125)

-d

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 2:48 pm

Joined: Tue Jan 18, 2011 6:17 am
...

Last edited by bish on Wed Feb 26, 2014 7:23 am, edited 2 times in total.

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 2:50 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
No, he's looking for a fraction where the repeating part is as long as possible in 1/3=0.33333333... the length of the repeating part is only 1, for 1/7=0.142857142857 the repeating part is 142857, which has length 6.

The period of the decimal expansion of a fraction is unbounded. Consider any real number with an infinite expansion that is repeating. It is clear that it's possible to find a real number that has an arbitrarily large period in it's decimal expansion, since we can just define it by taking some suitable (1) natural number n and writing x = 0.nnnnnnn..., which is a converging series and by the completeness of R, must be in it.

So the number we just constructed of the form 0.nnnnnnn... is a fraction and since we can construct such numbers with arbitrarily long period, there is no bound on the period of the decimal expansion of a fraction.

(1) By suitable, the natural number should not be repeating, ie 1212 is not suitable but 1221 is. We can easily find a suitable number of any length as 12222...222221.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 3:40 pm

Joined: Wed Apr 01, 2009 2:59 pm
TomZ wrote:
No, he's looking for a fraction where the repeating part is as long as possible in 1/3=0.33333333... the length of the repeating part is only 1, for 1/7=0.142857142857 the repeating part is 142857, which has length 6.

The period of the decimal expansion of a fraction is unbounded. Consider any real number with an infinite expansion that is repeating. It is clear that it's possible to find a real number that has an arbitrarily large period in it's decimal expansion, since we can just define it by taking some suitable (1) natural number n and writing x = 0.nnnnnnn..., which is a converging series and by the completeness of R, must be in it.

So the number we just constructed of the form 0.nnnnnnn... is a fraction and since we can construct such numbers with arbitrarily long period, there is no bound on the period of the decimal expansion of a fraction.

(1) By suitable, the natural number should not be repeating, ie 1212 is not suitable but 1221 is. We can easily find a suitable number of any length as 12222...222221.

For an even easier to see example, the reciprocal of a string of n nines has decimal expansion 0.[[n-1 zeros]] 1 [[n-1 zeros]] 1 [[n-1 zeros]] 1...

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 4:01 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Well, there you go, the simple proofs are always the best. But at least mine looks impressive

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Thu Jul 07, 2011 10:55 pm

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
I think I'm missing something. So out of all the fractions 1/X where X is an Integer between 1 and 100 which X has the longest sequence prior to the sequence repeating?

-d

Top

 Post subject: Re: fractions puzzlePosted: Fri Jul 08, 2011 1:46 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Oh sorry, I missed the part of you wanting to look just at the fractions 1/1...1/100 and assumed that you wanted to consider all fractions.

Just taking some theorems from Wikipedia, it's easy to see that 1/97 with period 96 has the decimal expansion with the longest period of the fractions in 1/1....1/100. First off, we do not need to consider any fraction greater than 1/97 because the period of 1/n is strictly less than n, so the period of 1/96 would be at most 95 which is less than the 96 we have. So we just need to check 98, 99, 100. 1/98=1/2*1/49, we can see that the period of the expansion must be less than that of 1/49, so less than 49 - this does not beat the 96 we have. As bish stated, 1/99 would have period 2. Finally 1/100 = 1/2*1/50 must have period less than 50.
So 1/97 is the fraction in 1/1....1/100 that has the longest repeating decimal expansion with period 96.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Fri Jul 08, 2011 11:19 am

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
That works, thanks!

-d

Top

 Post subject: Re: fractions puzzlePosted: Fri Jul 08, 2011 6:25 pm

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM

EDIT: Nevermind. I was thinking something else.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z

Last edited by Jorbs3210 on Sat Jul 09, 2011 9:45 pm, edited 1 time in total.

Top

 Post subject: Re: fractions puzzlePosted: Sat Jul 09, 2011 2:47 am

Joined: Sun Nov 23, 2008 2:18 am
To ask a more generalized question:

N is an integer such that 1/N is an infinite repeating decimal.
PN is the length of the repeating digit sequence in 1/N.
k is an integer such that 1/k has Pk > PN for any N<k

What are the values for k and Pk? Can these sequences be calculated without brute force? Do these sequence happen to be list in the OEIS?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 10:44 am

Joined: Mon Oct 18, 2010 10:48 am
Theoretically shouldn't it be the fraction with the largest prime number in the denominator?

_________________
++Noah (NType3 here, Emrakul elsewhere)

Moderator for Puzzling Stack Exchange - a new site for specific puzzling questions!

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 11:01 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
There is no largest prime number.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 12:07 pm

Joined: Mon Oct 18, 2010 10:48 am
There is if you have an upper bound, e.g. from 1/1 to 1/100, which was the question.

_________________
++Noah (NType3 here, Emrakul elsewhere)

Moderator for Puzzling Stack Exchange - a new site for specific puzzling questions!

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 2:04 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Jerry's problem does not specify an upper bound (since Darryl's question has been answered I assumed your answer to be for that) or one could assume Jerry to be looking for the smallest number that satisfies his properties.

But it's incorrect either way. In the case 6 is the upper bound, 5 would be the largest prime but it has a finite decimal expansion (which means period 0?) while 1/3 has period 1. Or for upper bound 101, 1/101 has period 4 but 1/97 has period 96.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 2:38 pm

Joined: Sun Nov 23, 2008 2:18 am
NType3 wrote:
Theoretically shouldn't it be the fraction with the largest prime number in the denominator?

Limiting N to prime values, the first few values of 1/N are(repeating sequence unlined):
1/2 = .5
1/3 = .3
1/5 = .2
1/7 = .142857
1/11 = .09
1/13 = .076923
1/17 though 1/31 have long decimal expansions
1/37 = .027
1/41 = .02439
1/43 though 1/97 have long decimal expansions

With periods of: {}, 1, {}, 6, 2, 6. ..., 3, 5.

As defined in my previous post, it might be that k has to be prime, but primality is not sufficient.

The first few values of k would be: 3, 7, and 17, but I cannot test any larger values of N without a more precise calculator.

Anyone know a good online calculator that can do really long decimal expansions?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: fractions puzzlePosted: Sun Jul 10, 2011 2:42 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Wolfram Alpha does a pretty good job at it. It tells you exactly what the period is.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: fractions puzzlePosted: Wed Jul 13, 2011 8:00 am

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
Let's examine 1/7 for example.
Multiply 1/7 by 10, to get 1+3/7. So the first digit in the expansion is 1.
Multiply 3/7 by 10, to get 4+2/7. So the second digit in the expansion is 4.
Multiply 2/7 by 10, to get 2+6/7. So the third digit in the expansion is 2.
Multiply 6/7 by 10, to get 8+4/7. So the fourth digit in the expansion is 8.
Multiply 4/7 by 10, to get 5+5/7. So the fifth digit in the expansion is 5.
Multiply 5/7 by 10, to get 7+1/7. So the sixth digit in the expansion is 7.
We are now back to 1/7, so the whole cycle starts again.

As you can see, all six possible fractions x/7 occur.

Now lets try it with 1/13.
Multiply 1/13 by 10, to get 0+10/13. So the first digit in the expansion is 0.
Multiply 10/13 by 10, to get 7+9/13. So the second digit in the expansion is 7.
Multiply 9/13 by 10, to get 6+12/13. So the third digit in the expansion is 6.
Multiply 12/13 by 10, to get 9+3/13. So the fourth digit in the expansion is 9.
Multiply 3/13 by 10, to get 2+4/13. So the fifth digit in the expansion is 2.
Multiply 4/13 by 10, to get 3+1/13. So the sixth digit in the expansion is 3.
and we're back to 1/13, and the cycle starts again.

So even though there are 12 possible fractions x/13, which could have resulted in 12 repeated digits, we've seen only 6 before it started repeating.

The interesting thing is that if you now start with 2/13, one of the missing fractions, then you also get a sequence of 6 steps. It is essentially the same as the above sequence but everything doubled in some sense (modulo 13 if that means anything to you). You can prove that all the sequences that you could get are the same length since they are all multiples of each other. Therefore, the length of the sequence must divide the number of possible fractions you have.

For example, for any prime p (except 2 or 5), the length of the repeating decimals of 1/p will divide p-1.

For 1/p (p prime) to have repeating decimal of length p-1, we need 10 to be a so called primitive root modulo p. The actual definition of 10 being a primitive root modulo p is that 10, 10^2, ..., 10^(p-1) all have different remainders after division by p. This is simply another way of saying that the procedure I described above, done for p-1 steps, results in p-1 different fractions.

There is no simple way to predict which primes p have 10 as a primitive root as far as I know. The only way is to calculate the period and see, or for large p it is quicker to check that the period is not any of the strict divisors of p-1.

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/

Top

 Post subject: Re: fractions puzzlePosted: Wed Jul 13, 2011 7:46 pm

Joined: Sun Nov 23, 2008 2:18 am
Assuming primality is required for the period of 1/k being greater than the period of all 1/n for n < k, the values of k less than 100 are:

3, 7, 17, 19, 23, 29, 47, 59, 61, 97.

Also, with the exception of three, all of these have periods equal to k-1.

Removing three gives A001913.
Replacing three with 2 gives A006883

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 20 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic