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

Applet
 

:bow:
Excellent work Dario and your factorisation applet is superb. I must put good use to it
You are well worth your salt.
Keep up the good work and all the best.
Mally :coffee:

A sequel to Number 100
 

[QUOTE=fetofs]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]
:smile:
It is pretty obvious that not only number 100 but also all numbers up to 100 excepting 1,2,3,4, can be written by mixed fractions with the same rules
Eg : 9 + 5472/1368 = 13.
The tough nuts to crack are 15 and 18 though these may be solved as a simple fraction.
To stick to mixed fractions we must assume a whole number +..x/y using all the 9 digits. There is a way to adhere to this rule.
Can you give it? I mean the mixed fractions for 15 and 18?
Mally :coffee:

[QUOTE=mfgoode]:smile:
It is pretty obvious that not only number 100 but also all numbers up to 100 excepting 1,2,3,4, can be written by mixed fractions with the same rules
[/QUOTE]
I've computed all solutions up to 100 using the following (PARI) program:
[CODE]
sol=vector(100,i,0);A=matrix(100,300);b=c=vector(9);for(n=1,9!,u=numtoperm(9,n);a=0;\
x=0;for(i=1,9,x=10*x+u[10-i];c[10-i]=x);for(i=0,2,x=0;for(j=i+1,9,x=10*x+u[j];b[j]=x);\
for(j=i+1,8,x=a+b[j]/c[j+1];if((x<=100)&&(type(x)=="t_INT"),sol[x]++;y=sol[x];\
A[x,3*y-2]=a;A[x,3*y-1]=b[j];A[x,3*y]=c[j+1]));a=10*a+u[i+1]));\
for(i=1,100,for(j=1,sol[i],write("mixed.txt",i,"=",A[i,3*j-2],"+",A[i,3*j-1],"/",A[i,3*j])))
[/CODE]

See mixed.txt for the solutions.

[QUOTE=R. Gerbicz]I've computed all solutions up to 100 using the following (PARI) program:
[CODE]
sol=vector(100,i,0);A=matrix(100,300);b=c=vector(9);for(n=1,9!,u=numtoperm(9,n);a=0;\
x=0;for(i=1,9,x=10*x+u[10-i];c[10-i]=x);for(i=0,2,x=0;for(j=i+1,9,x=10*x+u[j];b[j]=x);\
for(j=i+1,8,x=a+b[j]/c[j+1];if((x<=100)&&(type(x)=="t_INT"),sol[x]++;y=sol[x];\
A[x,3*y-2]=a;A[x,3*y-1]=b[j];A[x,3*y]=c[j+1]));a=10*a+u[i+1]));\
for(i=1,100,for(j=1,sol[i],write("mixed.txt",i,"=",A[i,3*j-2],"+",A[i,3*j-1],"/",A[i,3*j])))
[/CODE]
[/QUOTE]

I hereby officially present R. Gerbicz with the award of making the most extremely obscure programs!

Fantastic!
 

[QUOTE=R. Gerbicz]I've computed all solutions up to 100 using the following (PARI) program:
[CODE]
sol=vector(100,i,0);A=matrix(100,300);b=c=vector(9);for(n=1,9!,u=numtoperm(9,n);a=0;\
x=0;for(i=1,9,x=10*x+u[10-i];c[10-i]=x);for(i=0,2,x=0;for(j=i+1,9,x=10*x+u[j];b[j]=x);\
for(j=i+1,8,x=a+b[j]/c[j+1];if((x<=100)&&(type(x)=="t_INT"),sol[x]++;y=sol[x];\
A[x,3*y-2]=a;A[x,3*y-1]=b[j];A[x,3*y]=c[j+1]));a=10*a+u[i+1]));\
for(i=1,100,for(j=1,sol[i],write("mixed.txt",i,"=",A[i,3*j-2],"+",A[i,3*j-1],"/",A[i,3*j])))
[/CODE]

See mixed.txt for the solutions.[/QUOTE]
:bow:
Excelent R. Gerbicz
However the number 15 you have given as 15=0+27945/1863 but this is not a mixed fraction which is of the form a + b/c :flex: so 0 is not permissible as it does not qualify as a whole number.

The other is 18 in the same form but you have omitted it altogether!

Hint: Your computer and PARI program is right no doubt and I am merely pointing for a gimmicky way of writing the mixed fraction which IS a complex fraction but it qualifies as a mixed fraction.
Please try it out and dont swear at me as it is so very simple!
Mally

[QUOTE="mfgoode"]0 is not permissible as it does not qualify as a whole number.[/QUOTE]Strange, I was taught that whole numbers started at 0 and natural numers started at 1.

retina is right. Please see this Wikipedia article about [URL="http://en.wikipedia.org/wiki/Whole_number"]whole number[/URL].

Zero
 

[QUOTE=retina]Strange, I was taught that whole numbers started at 0 and natural numers started at 1.[/QUOTE]

:smile: Good point Retina!

However I made it very clear in my previous post on distinguishing between a simple fraction b/c and a mixed fraction a +b/c. If you make a=0 then there will be no difference. And here I mean that 'a' has a value and NOT zero.

To avoid ambiguity I used the old term which was in use before the idea of sets and the empty set was conceived when the zero came into prominence.

So lets not quibble over definitions, neither should one be dogmatic, Alpertron, when the solution of the problem is what is required.

And in this regard my hint is that the solution, by the way, is a complex fraction such as a+ (b)/(c/d). If I do go further I will give the game away but I will, if R.Gerbicz does not arrive at the solution. He deserves it after the pains he has taken over it.

Well lets have the final word from Wikipedia which we all seem to follow these days. No wonder Wiki has an edit section!

"Peano axioms. There are many systems that satisfy these axioms, including the natural numbers (either starting from zero or one)".[extract from Wiki]

I hope that this is clear but I will welcome any negative suggestions on the non negative integers where zero is included to distinguish it from the Natural or whole numbers now known as the positive integers.

I thank you and Alpertron to bring this delicate point up and in this case it is worth splitting hairs.

Mally :coffee:

This time it appears that Mally is right. The original problem in post #1 was:

[QUOTE="mfgoode"]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.[/QUOTE]
So in this extension (replacing the value 100 by other numbers) no zeros are allowed, only the digits 1 to 9 with no repetition. This invalidates all solutions of the form 0 + abcde/fghi .

[QUOTE=mfgoode]
And in this regard my hint is that the solution, by the way, is a complex fraction such as a+ (b)/(c/d).[/QUOTE]
OK, I've computed all "complex" solutions up to 100 by the following (PARI) program
[CODE]
sol=vector(100,i,0);A=matrix(100,1000);b=matrix(9,9);for(n=1,9!,u=numtoperm(9,n);\
for(i=1,9,x=0;for(j=i,9,x=10*x+u[j];b[i,j]=x));\
for(i=1,2,for(j=i+1,7,for(k=j+1,8,x=b[1,i]+b[i+1,j]/(b[j+1,k]/b[k+1,9]);\
if((x<=100)&&(type(x)=="t_INT"),sol[x]++;y=4*sol[x];\
A[x,y-3]=b[1,i];A[x,y-2]=b[i+1,j];A[x,y-1]=b[j+1,k];A[x,y]=b[k+1,9])))));\
for(i=1,100,for(j=1,sol[i],y=4*j;\
write("complex.txt",i,"=",A[i,y-3],"+",A[i,y-2],"/(",A[i,y-1],"/",A[i,y],")")))
[/CODE]

You can see the solutions in complex.txt file.

[QUOTE=alpertron]This invalidates all solutions of the form 0 + abcde/fghi .[/QUOTE]
Yes, you're right.

Number 100
 

:smile: :bow:
Well R.Gerbicz you have it got it right this time. Congratulations!
Thanks Alpertron for elucidating my point on the mixed fractions.
The specific ones I had for 15 and 18 are
15 = 3 + 8952/746/1 and yours is even better 3 + 1/746/8952.
The other was
18 = 9 + 5742/638/1 which you have given as 9 + 1/638/5742
Your attachment giving all the values is amazing and gives me the incentive that I could put my computer to better use.
I hope to get another p.c. which I may devote to joining in primes search and the various kinds you people post about.
Thank you, and I think we could put a lid on this thread.
Mally :coffee: