Number 100

mfgoode · 2006-08-07, 17:13

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

R. Gerbicz · 2006-08-07, 17:41

Are parentheses allowed?

fetofs · 2006-08-07, 23:10

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

drew · 2006-08-08, 04:38

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.

mfgoode · 2006-08-08, 07:37

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

R. Gerbicz · 2006-08-08, 09:33

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.

Kees · 2006-08-08, 11:11

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 ?

mfgoode · 2006-08-08, 15:25

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

alpertron · 2006-08-08, 18:50

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).

R. Gerbicz · 2006-08-08, 19:11

This is a well known sequence, see http://en.wikipedia.org/wiki/Sylvester's_sequence
including some more factorizations also.

alpertron · 2006-08-08, 21:41

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*10⁹.

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).

u² - u + 1 = 0

Let u = t+b.

(t+b)² - (t+b) + 1 = 0
t² + 2bt + b² - t - b + 1 = 0
t² + (2b - 1)t + b² - b + 1 = 0

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

t² + 1/4 - 1/2 + 1 = 0
t² + 3/4 = 0
4t² + 3 = 0

Let w = 2t:

w² + 3 = 0
w² = -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).

2006-08-07, 17:13	#1
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×3³×19 Posts	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

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

2006-08-07, 17:41	#2
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 23×71 Posts	Are parentheses allowed?

2006-08-08, 11:11	#7
Kees Dec 2005 2²×7² Posts	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 ?

2006-08-08, 18:50	#9
alpertron Aug 2002 Buenos Aires, Argentina 2·761 Posts	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).

2006-08-08, 19:11	#10
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 23×71 Posts	This is a well known sequence, see http://en.wikipedia.org/wiki/Sylvester's_sequence including some more factorizations also.

2006-08-08, 21:41	#11
alpertron Aug 2002 Buenos Aires, Argentina 5F2₁₆ Posts	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*10⁹. 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). u² - u + 1 = 0 Let u = t+b. (t+b)² - (t+b) + 1 = 0 t² + 2bt + b² - t - b + 1 = 0 t² + (2b - 1)t + b² - b + 1 = 0 Let 2b - 1 = 0, so b = 1/2 (valid because gcd(p,2)=1). t² + 1/4 - 1/2 + 1 = 0 t² + 3/4 = 0 4t² + 3 = 0 Let w = 2t: w² + 3 = 0 w² = -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).