## A whole lot of 1's

DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

### A whole lot of 1's

Okay, this is a toughie. In fact, I couldn't solve it myself and had to look at the answer. Still, I have some faith in the brainpower available here. So:

Does a whole number exist which consists of all 1's and where 1999 is a divisor? Prove your answer (without using a computer, ceptimus!).
Cool Hand
Posts: 10000
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain

### Re: A whole lot of 1's

DanishDynamite wrote:Okay, this is a toughie. In fact, I couldn't solve it myself and had to look at the answer. Still, I have some faith in the brainpower available here. So:

Does a whole number exist which consists of all 1's and where 1999 is a divisor? Prove your answer (without using a computer, ceptimus!).
Here's an even tougher problem for you, DD. Where does this thread belong?

Oh, I don't know--Science, Mathematics & Technology maybe?

:D

Cool Hand
Beleth
Posts: 2868
Joined: Tue Jun 08, 2004 8:55 pm
Location: That Good Night
If the product is going to end in a 1, the multiplicand is going to have to end in a 9. 1999 x ...9 = ...1

Now, 1999 x 9 = 17,991, so the tens digit of the multiplicand is going to have to add 2 to the tens digit of the product. The only number that fills the bill is 8. 1999 x ...89 = ...11.

Through trial and error, I got the following sequence:

1999 x 9 = 17,991
1999 x 89 = 177,911
1999 x 889 = 1,777,111
1999 x 6,889 = 13,771,111
1999 x 66,889 = 133,711,111
1999 x 666,889 = 1,333,111,111
1999 x 2,666,889 = 5,331,111,111

It is at this point that the 9 key broke on my calculator so I tried another tack. I looked at the number left over after you removed the string of 1's at the end.

1799
1779
1777
1377
1337
1333
533

This sequence is monotonically decreasing. Sometimes not very fast, but always decreasing. It's also always an odd number. So eventually it will shrink to 1. When that happens, the whole string will be 1's.

So yes, there is a whole number that consists entirely of 1's where 1999 is a divisor.

I am glad that you didn't ask what that number was. I can state with confidence, however, that if my reasoning is correct, it will have less than ceil( 533 / 2 ) + 7 = 274 1's in it.

And this definitely belongs in the Puzzles section.

Edit --
Ignore, this, I'm full of crap.
Brown
Posts: 297
Joined: Wed Jun 09, 2004 3:15 pm
My first reaction is to say that a whole number exist that consists of AN EVEN NUMBER OF 1's cannot have 1999 as a divisor. The proof is simple. Any whole number consisting of AN EVEN NUMBER OF 1's must be divisible by 11, but 1999 is not divisible by 11.

Now, moving on to whole numbers exist that consist of AN ODD NUMBER OF 1's ....
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

### Re: A whole lot of 1's

DanishDynamite wrote:Does a whole number exist which consists of all 1's and where 1999 is a divisor? Prove your answer (without using a computer, ceptimus!).
Yes, such a number exists.

<table><tr bgcolor="#c0c0e0"><td> Spoiler - 'select' text using mouse, or press Ctrl-A to reveal. </td></tr><tr bgcolor="white"><td>

One such number is a string of 1998 ones. And this is true for any integer number base greater than one that is co-prime to 1999.

<blockquote>sidebar - Let me introduce a shorhand notation here. Let 1#1998 represent a string of 1998 ones.

Or in general, for any integer base b greater than one, where n<b, then n#m means a string of length m of the digit n.

In summation notation:

n#m = sum (k=0 to m-1) { n * b^k }

examples in base ten:

1#7 = 1111111
9#12 = 999999999999
</blockquote>

Since 1999 is a prime number, Fermat's Little Theorem is a good starting point for a proof that 1999 divides 1#1998.

http://mathworld.wolfram.com/FermatsLittleTheorem.html

From Fermat, we know that 1999 divides (a^1998) - 1.

Let's choose a = 10, which will work since 10 and 1999 are co-prime.

Then (10^1998) - 1 = 9#1998 = 9 * 1#1998.

Since 1999 does not divide 9, then it must divide 1#1998.

qed.

disclaimer - despite that I have checked my work, typos in the above proof may still exist.
</td></tr></table>
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Brown wrote:My first reaction is to say that a whole number exist that consists of AN EVEN NUMBER OF 1's cannot have 1999 as a divisor. The proof is simple. Any whole number consisting of AN EVEN NUMBER OF 1's must be divisible by 11, but 1999 is not divisible by 11.
Um, there's a slight flaw in your "proof". :)

Counter-example:

11 and 1999 both divide 21989.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

### Re: A whole lot of 1's

On a related note:

<table><tr bgcolor="#c0c0e0"><td> Spoiler - 'select' text using mouse, or press Ctrl-A to reveal. </td></tr><tr bgcolor="white"><td>

Xouper's Corollary to Fermat:

If p is a prime number then p divides 1#(p-1), for any integer base b greater than one and b is coprime to p.

The proof is simlar to the answer given above.

Examples (I wish the html tag for subscripts was enabled on this forum, so consider the stuff between the square brackets to be a subscript indicating the base of the number.):

7 divides 111111[base 10].

7 divides 111111[base 16].

7 divides 111111[base 60].

7 divides 111111[any base>1 coprime to 7].

</td></tr></table>
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

### Re: A whole lot of 1's

Abdul Alhazred wrote:Good proof xouper, but I wonder can there be a smaller number that fills the bill? Not a small number per se, just smaller?
I wouldn't be at all surprised if there is. I just went for the easy win since the original puzzle did not ask for the smallest such number. It shouldn't take ceptimus long to program his computer to find such a number.

Code: Select all

n = 0;

for (i=1; i<upperlimit; i++) {

n = (n*10) + 1;
if (0 == n % 1999) then printf i;

}


:wink:
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

### Re: A whole lot of 1's

Cool Hand wrote:Here's an even tougher problem for you, DD. Where does this thread belong?

Oh, I don't know--Science, Mathematics & Technology maybe?

:D

Cool Hand
What would be ideal is if a single thread could be linked from more than one subforum, similar to the way usenet allows cross-posting. I have long wished for such a feature on these types of forums.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Beleth wrote:... This sequence is monotonically decreasing. Sometimes not very fast, but always decreasing. It's also always an odd number. So eventually it will shrink to 1. When that happens, the whole string will be 1's.

... I can state with confidence, however, that if my reasoning is correct, it will have less than ceil( 533 / 2 ) + 7 = 274 1's in it.

Edit -- Ignore, this, I'm full of crap.
I almost missed that "edit" :)

I assume you went back and did a few more iterations of your sequence:

Code: Select all

1999 *             9 = 17991
1999 *            89 = 177911
1999 *           889 = 1777111
1999 *          6889 = 13771111
1999 *         66889 = 133711111
1999 *        666889 = 1333111111
1999 *       2666889 =  5331111111
1999 *      22666889 =  45311111111
1999 *     222666889 =  445111111111
1999 *    4222666889 =  8441111111111
1999 *   34222666889 =  68411111111111
1999 *  334222666889 =  668111111111111
1999 * 7334222666889 = 14661111111111111

It seemed like such a promising approach, too.

These kinds of deviations from the initial pattern are not all that rare in mathematics and is why such a strategy is often considered to have little predictive value without a rigorous proof to back it up. They sometimes have value as an exploratory experiment, though.

Imagine, then, how Fermat might have felt had he lived to see his prime number sequence turn out not to be prime after the first five.

(2^(2^n)) +1 is a prime for n=0 to 4.

http://mathworld.wolfram.com/FermatPrime.html

Or worse, imagine Euler's disappointement at discovering his sequence of primes doesn't fail until after the 40th iteration.

Euler's formula, n^2 - n + 41 gives prime numbers for n = 1 to 40.

http://mathworld.wolfram.com/Prime-Gene ... omial.html
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Could you explain in short, easily digestable words, how this theorem shows that 1999 divides (a^1998) - 1.

I'm not disagreeing, I'm just asking for clarification. Thanks. :)
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self

Could you explain in short, easily digestable words, how this theorem shows that 1999 divides (a^1998) - 1.

I'm not disagreeing, I'm just asking for clarification. Thanks. :)
Sure, not a problem. I'm not sure how much explanation you are asking for, so forgive me if I provide too much and repeat some things you already know. Or maybe my explanation will seem too skimpy, in which case, we try again.

Fermat's theorem can be stated two different ways. The first way listed on mathworld is this (translated into english from the math notation):

a^p is congruent to a, modulo p

The second way is listed as statement number (3):

(a^(p-1)) - 1 is congruent to zero, modulo p

These two statements are equivalent, if a and p have no factors in common.

I used the second form, which by the definition of congruence, is equivalent to saying:

p divides (a^(p-1)) - 1

From there we simply substitute 1999 for p.

Perhaps the notions of congruence and modulo need further clarification.

See http://en.wikipedia.org/wiki/Modular_arithmetic
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
OK. Thanks xouper. It was the notation for congruence and its meaning which got me lost. Sorry, its been too long since my university days, let alone my high school days.

I hereby declare that xouper has solved the problem.

I shall now present the solution I read:

Consider 2000 different numbers all consisting of 1's. Two of these numbers will give the same modulo when divided by 1999. Hence, the difference between these two numbers will be divisible by 1999. This difference will have the form 1...10...0. Since 1999 doesn't have a common factor with a number of the type 10^n, 1999 must devide the part of the number in front of the 0's.

QED.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
DanishDynamite wrote:Consider 2000 different numbers all consisting of 1's. Two of these numbers will give the same modulo when divided by 1999. Hence, the difference between these two numbers will be divisible by 1999. This difference will have the form 1...10...0. Since 1999 doesn't have a common factor with a number of the type 10^n, 1999 must devide the part of the number in front of the 0's.
Nice.

In other words, there exist integers m>n>0 such that

1#m is congruent to 1#n, modulo 1999

(1#m - 1#n) is congruent to (1#n - 1#n), modulo 1999

(1#m - 1#n) is congruent to 0, modulo 1999

Thus, 1999 divides (1#m - 1#n)

1999 divides (1#(m-n)) * (10^n)

Since 1999 does not divide 10^n, it must divide 1#(m-n)

QED.

Using Fermat's theorem, we know that 1998 is one possible value for (m-n).

[mode="spinaltap"] My answer goes to eleven. [/mode] 8)

I eagerly await ceptimus's computational answer to the question whether there is a smaller value for (m-n) that will also work.
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
xouper wrote:I eagerly await ceptimus's computational answer to the question whether there is a smaller value for (m-n) that will also work.
D'Oh! I've not even thought about a program yet. DD only likes 'real mathematics' proofs. :)

I've got a BigInteger class somewhere...
Sentzeu
Posts: 102
Joined: Sat Aug 21, 2004 12:16 am
Uhm well I think we have a problem.

After putting in 1#1998 in a math program called derive and dividing it by 1999, I get the following.

111222333444555666777889000111222333444555666777889000111222
333444555666777889000111222333444555666777889000111222333444
555666777889000111222333444555666777889000111222333444555666
777889000111222333444555666777889000111222333444555666777889
000111222333444555666777889000111222333444555666777889000111
222333444555666777889000111222333444555666777889000111222333
444555666777889000111222333444555666777889000111222333444555
666777889000111222333444555666777889000111222333444555666777
889000111222333444555666777889000111222333444555666777889000
111222333444555666777889000111222333444555666777889000111222
333444555666777889000111222333444555666777889000111222333444
555666777889000111222333444555666777889000111222333444555666
777889000111222333444555666777889000111222333444555666777889
000111222333444555666777889000111222333444555666777889000111
222333444555666777889000111222333444555666777889000111222333
444555666777889000111222333444555666777889000111222333444555
666777889000111222333444555666777889000111222333444555666777
889000111222333444555666777889000111222333444555666777889000
111222333444555666777889000111222333444555666777889000111222
333444555666777889000111222333444555666777889000111222333444
555666777889000111222333444555666777889000111222333444555666
777889000111222333444555666777889000111222333444555666777889
000111222333444555666777889000111222333444555666777889000111
222333444555666777889000111222333444555666777889000111222333
444555666777889000111222333444555666777889000111222333444555
666777889000111222333444555666777889000111222333444555666777
889000111222333444555666777889000111222333444555666777889000
111222333444555666777889000111222333444555666777889000111222
333444555666777889000111222333444555666777889000111222333444
555666777889000111222333444555666777889000111222333444555666
777889000111222333444555666777889000111222333444555666777889
000111222333444555666777889000111222333444555666777889000111
222333444555666777889000111222333444555666777889000111222333
444555666777889/2

So either I screwed up (will anyone please check the results), or Xouper screwed up.

Funny thing is that it repeats (000111222333444555666777889) 74 times.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Sentzeu wrote:Uhm well I think we have a problem.

After putting in 1#1998 in a math program called derive and dividing it by 1999, I get the following.

(something) / 2

So either I screwed up (will anyone please check the results), or Xouper screwed up.

Funny thing is that it repeats (000111222333444555666777889) 74 times.
The really funny thing is that the result you got is equal to

(1#1998) / 1998

What tipped me off is that your result contained the fraction 1/2 which should never happen when dividing by 1999.

In Maple, I entered

sum('10^k', 'k'=0..1997) / 1999;

55583347229170140625868489800455783447279195153132
12161636373742426768940025568339725418264687899505
30820966038574842977044077594352731921516313712411
76143627369240175643377244177644377744427769440275
69340225668389750430770941026068589850480795953532
32171641376243677394252681896503807459285198154632
87199155133122116613862486798955033072091601356233
67239175143127119115113112111611361236173642376743
92751931521316213662386748930020565838474792952031
57134122616863987549330220665888499805458284697904
50780946028569840475793452281696403757434272691901
50630870991051081096103607359235173142126618864988
04958034572841976543827469290200655883497304207659
38524817964537824467789450280695903507309210160635
87349230170640875993552331721416263687399255183147
12912011561336223667389250180645878494802957034072
59185148129620365738424767939525318214662886999055
08309710410760936023567339225168139625368239675393
25218164637874492801956533822466788950030570840976
04357734422766939025068089600355733422266688900005
55833472291701406258684898004557834472791951531321
21616363737424267689400255683397254182646878995053
08209660385748429770440775943527319215163137124117
61436273692401756433772441776443777444277694402756
93402256683897504307709410260685898504807959535323
21716413762436773942526818965038074592851981546328
71991551331221166138624867989550330720916013562336
72391751431271191151131121116113612361736423767439
27519315213162136623867489300205658384747929520315
71341226168639875493302206658884998054582846979045
07809460285698404757934522816964037574342726919015
06308709910510810961036073592351731421266188649880
49580345728419765438274692902006558834973042076593
85248179645378244677894502806959035073092101606358
73492301706408759935523317214162636873992551831471
29120115613362236673892501806458784948029570340725
91851481296203657384247679395253182146628869990550
83097104107609360235673392251681396253682396753932
52181646378744928019565338224667889500305708409760
43577344227669390250680896003557334222666889

Notice that the least significant digits match what Beleth observed.
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
xouper wrote:
DanishDynamite wrote:Consider 2000 different numbers all consisting of 1's. Two of these numbers will give the same modulo when divided by 1999. Hence, the difference between these two numbers will be divisible by 1999. This difference will have the form 1...10...0. Since 1999 doesn't have a common factor with a number of the type 10^n, 1999 must devide the part of the number in front of the 0's.
Nice.

In other words, there exist integers m>n>0 such that

1#m is congruent to 1#n, modulo 1999

(1#m - 1#n) is congruent to (1#n - 1#n), modulo 1999

(1#m - 1#n) is congruent to 0, modulo 1999

Thus, 1999 divides (1#m - 1#n)

1999 divides (1#(m-n)) * (10^n)

Since 1999 does not divide 10^n, it must divide 1#(m-n)

QED.

Using Fermat's theorem, we know that 1998 is one possible value for (m-n).

[mode="spinaltap"] My answer goes to eleven. [/mode] 8)

I eagerly await ceptimus's computational answer to the question whether there is a smaller value for (m-n) that will also work.
Nicely restated. I found the proof very elegant as well, but you stated it better.

In this vein, how about having a go at my "Square of 16" puzzle? :)
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
A number comprising a string of 999 '1's is divisible by 1999

The result of the division is:

5558334722917014062586848980045578344727919515313212161636373
7424267689400255683397254182646878995053082096603857484297704
4077594352731921516313712411761436273692401756433772441776443
7774442776944027569340225668389750430770941026068589850480795
9535323217164137624367739425268189650380745928519815463287199
1551331221166138624867989550330720916013562336723917514312711
9115113112111611361236173642376743927519315213162136623867489
3002056583847479295203157134122616863987549330220665888499805
4582846979045078094602856984047579345228169640375743427269190
1506308709910510810961036073592351731421266188649880495803457
2841976543827469290200655883497304207659385248179645378244677
8945028069590350730921016063587349230170640875993552331721416
2636873992551831471291201156133622366738925018064587849480295
7034072591851481296203657384247679395253182146628869990550830
9710410760936023567339225168139625368239675393252181646378744
9280195653382246678895003057084097604357734422766939025068089
6003557334222666889

The first ten solutions occur at:

1#999
1#1998
1#2997
1#3996
1#4995
1#5994
1#6993
1#7992
1#8991
1#9990

I used java, as it has a built-in BigInteger class

Code: Select all

import java.math.BigInteger;

public class ones
{
public static void main(String[] args)
{
int length;

BigInteger BigZero;
BigInteger BigN;
BigInteger Big1999;
BigInteger BigRemainder;

BigZero = new BigInteger("0");
BigN = new BigInteger("1");
Big1999 = new BigInteger("1999");

for (length = 1; length < 10000; length++)
{
BigRemainder = BigN.remainder(Big1999);

if (BigRemainder.equals(BigZero))
{

System.out.print("Solution at ");
System.out.println(length);
System.out.println();
}

BigN = BigN.multiply(BigInteger.valueOf(10));
}

System.out.println("Finished");
}
}

DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
Fabulous stuff, ceptimus!

I hereby forgive you for using a computer to arrive at the specific answer you did.

Well done (in this case)!

:)
Sentzeu
Posts: 102
Joined: Sat Aug 21, 2004 12:16 am
Thanks ceptimus I knew the error had to be that but I have to admit that I forgot to go back and redo it, was busy with other math problems.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
ceptimus wrote:A number comprising a string of 999 '1's is divisible by 1999

The result of the division is:

55583347229...7334222666889
In hindsight, if one looks at the result from Maple that I posted previously for (1#1998)/1999, it contains two complete copies of the result for (1#999)/1999. No surprise there, but I didn't think to look.
The first ten solutions occur at:

1#999
1#1998
1#2997
1#3996
1#4995
1#5994
1#6993
1#7992
1#8991
1#9990
Part two of this puzzle:

Is the following true or false and can you prove it?

If and only if k is a positive integer, then 1999 divides 1#(k*999).

If true, this cannot be proven by brute force computation, since k can be any of infinitely many values.

You can use the fact that 999 is the smallest n>0 such that 1999 divides 1#n, since that fact has already been established by ceptimus's computations.

Part three of the puzzle:

Is there a simple algorithm that will find the smallest n>0 such that 1999 divides 1#n, without using any kind of "big integer" data types, i.e. can be done using only 16 bit integers? No need to find the result of the division, just find the number n.

To test your algorithm, also find the smallest n such that 1997 divides 1#n.
Posts: 698
Joined: Sat Jun 05, 2004 4:53 pm
xouper wrote: Part two of this puzzle:

Is the following true or false and can you prove it?

If and only if k is a positive integer, then 1999 divides 1#(k*999).

If true, this cannot be proven by brute force computation, since k can be any of infinitely many values.

You can use the fact that 999 is the smallest n>0 such that 1999 divides 1#n, since that fact has already been established by ceptimus's computations.

.
I think I can do the easy half of this 'if and only if'. That is, if k is a positive integer, then 1999 divides 1#(k*999).

1) We know that 1999 divides 1#999, therefore we know that it is true for k = 1.

2) Now assume it is true for all positive integers, k, i.e. 1999 divides 1#(k*999) for all positive integers k.

3) Now to prove that IF it is true for k, THEN it is true for k +1.

1#((k+1)*999) = [1#(k*999)]*10^999 + 1#999

Since 1999 divides 1#(k*999) (from our assumption) and 1999 divides 1#999, we know that 1999 also divides [1#(k*999)]*10^999 + 1#999.

4) Therefore, since it is true for k=1 AND we know that IF it is true for k THEN it is true for k+1, we can see by induction that it is true for all positive integer values of k.

Now, someone else prove it is ONLY true for positive integer values of k :D

Posts: 698
Joined: Sat Jun 05, 2004 4:53 pm
Wait, maybe I can get started....

n is a positive integer in all uses below. This all assumes 1#(k*999) for positive integer k, is divisible by 1999 for all k.

We start with the fact that 1#999 is the smallest value of n such that 1999 divides 1#n.

Therefore 1999 does not divide 1#n for n < 999.

But any n greater than 999, can be written like 1#(n-999)*10^999 + 1#999.

And then 1#(n-999) must be divisible by 1999 for 1#n to be divisible by 1999. This means that for no n between 999 and 1997 will 1999 divide 1#n (because the 1#(n-999) will be in the range 1#1 to 1#998, where none are divisible by 1999).

This proves that for all n < 1998, the only case where 1#n is divisible by 1999 is the case of 1#999.

Through similar reasoning, you can show that any n >1998 must be evenly divisible by 999 to have 1999 divide 1#n.

Take for instance n = 3000. This is 1#3000 which can be written as:

1#((3000-(3*999))*10^[3*999] + 1#[3*999] = 1#3*10^2997 + 1#(2997)

Since 1#3 is not divisible by 1999, neither is 1#3000. This can be generalised for any n. Just re-write the 1#n as:

1#((n - (k)(999))*10^[k*999] + 1#(k*999)

Where k is equal to integer value of n/999.

Therefore, only for values of n which are evenly divisible by 999 will 1999 divide 1#n.

I think that shows that 1999 will only divide 1#n when n is of the form k*999.

Any improvements or corrections welcome.

ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Part two:

You only have to look at the traditional way of performing long division, by hand, to see that 1999 divides 1#(k*999) (exactly) if and only if k is a positive integer.

Code: Select all

     00005558334
----------------
1999|111111111111...
9995
11161
9995
11661
9995
16661
15992
6691
5997
6941
5997
9441
7996
14451


You can see immediately that the quotient must begin 00005558334, for any number of '1's in the dividend, and we already know that this pattern comes to an end (with a zero remainder) after 999 digits.
Once a remainder of zero is encountered, we are effectively starting the long division all over again, so we are bound to get the same pattern of length 999 repeating.
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Part three:

Since I can (just about) do long division with my brain, and my brain is an old six-and-a-half bit unit, it shows that there is an algorithm that works out the length of the quotient (and dividend) using only 16 bit integers.

Here is such an algorithm:

Code: Select all

int main(int argc, char* argv[])
{
int denominator;
int remainder;
int quotient_length;

denominator = 1997;

remainder = quotient_length = 0;

do
{
while (remainder < denominator)
{
remainder = 10 * remainder + 1;
quotient_length++;
}

remainder %= denominator;

} while (remainder);

printf("%u\n", quotient_length);

return 0;
}
For your test case of 1997, this returns an answer of 998.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
ceptimus wrote:Part three:

Since I can (just about) do long division with my brain, and my brain is an old six-and-a-half bit unit, it shows that there is an algorithm that works out the length of the quotient (and dividend) using only 16 bit integers.
When I saw your reply about part two (about long division), I knew you also had the answer to part three. Well done. In fact, your algorithm is exactly what I had in mind. Although I specifically did not ask for it, your algorithm can be extended slightly to accumulate the result of the division in a string.
For your test case of 1997, this returns an answer of 998.
We now have two nice examples where a prime divides a string of ones that is half the length predicted by Xouper's Corollary to Fermat:
• In any integer base b greater than one, if p is a prime number coprime to both b and b-1, then p divides 1#(p-1).
Examples from that corollary:

1999 divides 1#1998
1997 divides 1#1996

And ceptimus found:

1999 divides 1#999
1997 divides 1#998

Another example:

2003 divides 1#2002 and 1#1001

Part Four of this puzzle:

These examples suggest the following revision to my corollary:
• In any integer base b greater than one, if p is a prime number coprime to both b and b-1, then p divides 1#m, where m=(p-1)/2.
Can anyone prove or disprove this?

<table><tr bgcolor="#c0c0e0"><td> Spoiler - 'select' text using mouse, or press Ctrl-A to reveal. </td></tr><tr bgcolor="white"><td>

We might wish at this point to explicitly exclude p=2 and p=3 from the corollary.

But that still won't help, since a nice big counter-example is all it takes to disprove it:

1993 divides 1#1992

1993 does not divide 1#996

The rest of this is just filler to make the spoiler box bigger.
</td></tr></table>
Cool Hand
Posts: 10000
Joined: Sun Jun 06, 2004 4:09 pm
Location: Earning my avatar in the rain
Ow! My head hurt after the first post. Why did you guys have to split it wide open?

:evil:

Cool Hand
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Cool Hand wrote:Ow! My head hurt after the first post. Why did you guys have to split it wide open?
To peek inside to see how much you remember from your degree in mathematics.

Legal jargon is even worse than math jargon. It has all the outward appearances of being English, but isn't. :D
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Cool Hand wrote:Ow! My head hurt after the first post. Why did you guys have to split it wide open?
This inspired me to start a thread in the Science and Mathematics forum:

http://www.skepticalcommunity.com/phpbb ... php?t=2225