mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2006-08-07, 17:13   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Question Number 100


We are all familiar with the Name Edouard Lucas.
Like many mathematicians he spent his leisure moments solving or compiling puzzles.
The following is one attributed to him. He found seven solutions and expressed doubts for any more ways. Actually today we know 11 ways and no more.

The Problem: To write 100 using all 9 digits (1 -- 9) in the form of a mixed number; Eg: 100 = 91 + 5742/638 or 91(5742/638) a mixed number and no repitiion of digits but just the nine.

If you can give more than seven you beat Lucas at his own game.

Mally
mfgoode is offline   Reply With Quote
Old 2006-08-07, 17:41   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101100102 Posts
Default

Are parentheses allowed?
R. Gerbicz is offline   Reply With Quote
Old 2006-08-07, 23:10   #3
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

1011010102 Posts
Default

Quote:
Originally Posted by R. Gerbicz
Are parentheses allowed?
Mally is talking about mixed numbers, of the form x + y/z; I don't see why we should allow parentheses here....

On a side note, I bet Lucas didn't have a computer!


94+1578/263 = 100
91+7524/836 = 100
3+69258/714 = 100
91+5823/647 = 100
96+1428/357 = 100
96+2148/537 = 100
82+3546/197 = 100
81+5643/297 = 100
81+7524/396 = 100
96+1752/438 = 100
91+5742/638 = 100

Last fiddled with by fetofs on 2006-08-07 at 23:34
fetofs is offline   Reply With Quote
Old 2006-08-08, 04:38   #4
drew
 
drew's Avatar
 
Jun 2005

17E16 Posts
Default

Quote:
Originally Posted by fetofs
On a side note, I bet Lucas didn't have a computer!
It really trivializes these problems, doesn't it.
drew is offline   Reply With Quote
Old 2006-08-08, 07:37   #5
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Question Computers!

Quote:
Originally Posted by drew
It really trivializes these problems, doesn't it.
It certainly does.

Fetofs has certainly got it straight off the bat!

Well rather than start a new thread and a new problem I'm presenting this one, a simple one, to which no computer is needed at all. Maybe a calculator at the most, if you go about it the right way. If you use a computer, the compilers from Cambridge Univ. recommend C++. Actually there is no need of this and I got it straight away. I am nil in it anyway!

Puzzle: Given the expression 1/p + 1/q + 1/r < 1

Find values of p, q, r, such that its the largest fraction but less than 1

p, q, r, are whole numbers and no other symbols, parenthesis etc. In other words no funny stunts!

Having said that, the use of a comp would be cheating and please try to prove the answer in some way or the other.

Kindly spoilerise your answers.

Mally
mfgoode is offline   Reply With Quote
Old 2006-08-08, 09:33   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×36 Posts
Default

Quote:
Originally Posted by mfgoode
Puzzle: Given the expression 1/p + 1/q + 1/r < 1

Find values of p, q, r, such that its the largest fraction but less than 1

The answer is 1/2+1/3+1/7=41/42
Proof
Let s=1/p+1/q+1/r and indirectly let 1>s>41/42.
We can suppose that 1<=p<=q<=r
If p=1 then s>=1, contradiction.
If p>3 then s<=1/4+1/4+1/4=3/4<41/42, contradiction.
If p=3 then case1: r=3, then s=1, contradiction.
case2: r>3, then s<=1/3+1/3+1/4=11/12<41/42, contradiction.
So we can suppose that p=2 ( There is no other case ).
If q=2, then s>=1, contradiction.
If q>4, then s<=1/2+2/5=9/10<41/42.
If q=4, then case1: r=4, then s=1, contradiction.
case2: r>4, then s<=1/2+1/4+1/5=19/20<41/42, contradiction.
So we can suppose that q=3. ( There is no other case).
If q<7, then s>=1/2+1/3+1/6=1, contradiction.
If q>7, then s<=1/2+1/3+1/8=23/24<41/42, contradiction.
So q=7, and for that s=1/p+1/q+1/r=41/42.
R. Gerbicz is offline   Reply With Quote
Old 2006-08-08, 11:11   #7
Kees
 
Kees's Avatar
 
Dec 2005

19610 Posts
Default


Continuing this train of thought the values for s,t,u etc will be
x[1]=2
x[n]=1/(1-PROD(1/x[i]))+1
So s=43, t=1807


The obvious lurking question: which numbers in this sequence are prime ?

Kees is offline   Reply With Quote
Old 2006-08-08, 15:25   #8
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Thumbs up Number 100

Quote:
Originally Posted by Kees

Continuing this train of thought the values for s,t,u etc will be
x[1]=2
x[n]=1/(1-PROD(1/x[i]))+1
So s=43, t=1807


The obvious lurking question: which numbers in this sequence are prime ?


Well Kees thats an interesting train of thought and u should be in the region of 9 digits long at least. However, t breaks the prime run and I doubt very much if there will be any more primes at all. after s
Still I would like it worked out for a few more digits v,w,x.... to make a conjecture.
Mally
mfgoode is offline   Reply With Quote
Old 2006-08-08, 18:50   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54416 Posts
Default

Using my factorization applet in batch mode I found:

2 = 2

3 = 3

7 = 7

43 = 43

1807 = 13 * 139

3263443 = 3263443

10650056950807 = 547 * 607 * 1033 * 31051

113423713055421844361000443 = 29881 * 67003 * 9119521 * 6212157481

12864938683278671740537145998360961546653259485195807 = 5295435634831 * 31401519357481261 * 77366930214021991992277

165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 = 181 * 1987 * 112374829138729 * 114152531605972711 * 35874380272246624152764569191134894955972560447869169859142453622851

Since the next member in the sequence is about the square of the previous one (like the Fermat number sequence), I think that there are no other primes (or maybe only one more).
alpertron is offline   Reply With Quote
Old 2006-08-08, 19:11   #10
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101100102 Posts
Default

This is a well known sequence, see http://en.wikipedia.org/wiki/Sylvester's_sequence
including some more factorizations also.
R. Gerbicz is offline   Reply With Quote
Old 2006-08-08, 21:41   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54416 Posts
Default

I started my program to find small factors before trying to find the sequence in other Web site (anyway this is OK in the Puzzles forum).

These are the small prime factors I found with a program written in C:

k=0: 2
k=1: 3
k=2: 7
k=3: 43
k=4: 13, 139
k=5: 3263443
k=6: 547, 607, 1033, 31051
k=7: 29881, 67003, 9119521
k=9: 181, 1987
k=10: 2287, 2271427
k=11: 73
k=13: 52387, 5020387
k=14: 13999, 74203, 9638659, 57218683
k=15: 17881
k=16: 128551
k=17: 635263, 1286773, 21269959
k=20: 352867
k=21: 387347773, 1620516511
k=23: 74587
k=26: 27061
k=27: 164299, 3229081
k=28: 20929
k=29: 1171, 298483, 97562299
k=31: 1679143
k=34: 120823, 447841
k=35: 2408563
k=36: 38218903, 818864029
k=37: 333457, 117602053
k=38: 30241
k=39: 4219, 1372512301
k=40: 1085443, 156507607, 171818923
k=41: 7603
k=42: 1861, 84819199
k=44: 23773, 290791
k=45: 51769
k=46: 1285540933
k=47: 429547, 196973983
k=51: 179585227
k=53: 9829
k=57: 763176709
k=59: 2029, 38329, 320329, 3567469
k=61: 50023, 1445860807
k=64: 1459, 11234941
k=65: 72091, 609421
k=67: 245563, 3346633, 343870981
k=68: 6367063
k=69: 12763
k=70: 384061
k=71: 3799489, 8401963
k=73: 11844787
k=74: 35869
k=75: 20161, 42428887
k=76: 123427, 160200259
k=79: 51973, 195502537
k=80: 2437
k=82: 6230971
k=86: 9436201
k=88: 151477
k=89: 41077, 2171593
k=92: 15373, 21661, 1386013
k=93: 429446209
k=94: 12593197
k=95: 535879
k=96: 1407223, 1143074323
k=98: 20479

The value k is the index of the sequence. The upper bound is 2*109.

I also found that the prime factors greater than 3 must be congruent to 1 (mod 6):

Let p be a prime factor of a member of Sylvester's sequence greater than 3 (all equal signs below are congruences mod p).

u2 - u + 1 = 0

Let u = t+b.

(t+b)2 - (t+b) + 1 = 0
t2 + 2bt + b2 - t - b + 1 = 0
t2 + (2b - 1)t + b2 - b + 1 = 0

Let 2b - 1 = 0, so b = 1/2 (valid because gcd(p,2)=1).

t2 + 1/4 - 1/2 + 1 = 0
t2 + 3/4 = 0
4t2 + 3 = 0

Let w = 2t:

w2 + 3 = 0
w2 = -3

-3 is a quadratic residue mod p. Since -3 is congruent to 1 (mod 4), from the law of quadratic reciprocity we get that p is a quadratic residue mod -3 (or 3). This implies that p = 1 (mod 3).

So all prime factors of Sylvester's sequence greater than 3 must be congruent to 1 (mod 6).
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding multiples of a real number that are close to a whole number mickfrancis Math 16 2017-03-01 07:17
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Estimating the number of prime factors a number has henryzz Math 7 2012-05-23 01:13
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28

All times are UTC. The time now is 00:30.

Sat Apr 17 00:30:15 UTC 2021 up 8 days, 19:11, 0 users, load averages: 1.27, 1.49, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.