Number 100
 

:smile:
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 :coffee:

Are parentheses allowed?

[QUOTE=R. Gerbicz]Are parentheses allowed?[/QUOTE]

Mally is talking about mixed numbers, of the form [tex]x + y/z[/tex]; I don't see why we should allow parentheses here....

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

[spoiler]
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
[/spoiler]

[QUOTE=fetofs]On a side note, I bet Lucas didn't have a computer![/QUOTE]
It really trivializes these problems, doesn't it. :wink:

Computers!
 

[QUOTE=drew]It really trivializes these problems, doesn't it. :wink:[/QUOTE]

:smile: 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 :coffee:

[QUOTE=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
[/QUOTE]

[SPOILER]
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.
[/SPOILER]

[spoiler]
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
[/spoiler]

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

:cat:

Number 100
 

[QUOTE=Kees][spoiler]
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
[/spoiler]

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

:cat:[/QUOTE]
:smile:
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 :coffee:

Using [URL="http://www.alpertron.com.ar/ECM.HTM"]my factorization applet[/URL] in batch mode I found:

[B]2 = 2[/B]

[B]3 = 3[/B]

[B]7 = 7[/B]

[B]43 = 43[/B]

1807 = 13 * 139

[B]3263443 = 3263443[/B]

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

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

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[sup]9[/sup].

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[sup]2[/sup] - u + 1 = 0

Let u = t+b.

(t+b)[sup]2[/sup] - (t+b) + 1 = 0
t[sup]2[/sup] + 2bt + b[sup]2[/sup] - t - b + 1 = 0
t[sup]2[/sup] + (2b - 1)t + b[sup]2[/sup] - b + 1 = 0

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

t[sup]2[/sup] + 1/4 - 1/2 + 1 = 0
t[sup]2[/sup] + 3/4 = 0
4t[sup]2[/sup] + 3 = 0

Let w = 2t:

w[sup]2[/sup] + 3 = 0
w[sup]2[/sup] = -3

-3 is a quadratic residue mod p. Since -3 is congruent to 1 (mod 4), from the [URL="http://www.mersennewiki.org/index.php/Law_of_quadratic_reciprocity"]law of quadratic reciprocity[/URL] 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).