## A whole lot of 1's

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]

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: 1166
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)!

Abdul Alhazred
Posts: 77383
Joined: Mon Jun 07, 2004 1:33 pm
Title: Yes, that one.
Location: Chicago
ceptimus wrote: I used java, as it has a built-in BigInteger class
Slightly off topic, but would you happen to know how BigInteger is implemented? Something slick such as a linked list? Or does it just allocate some arbitrarily large block of memory?

Thanks.

So I was technically right about multiplying 1998 by powers of two, but had tunnel vision. Any multiple of 999, it seems.
The arc of the moral universe bends towards chaos.
People who believe God or History are on their side provide the chaos.

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: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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

If there is a sin against life, its consists perhaps not so much in despairing of life as in hoping for another life in eluding the implacable grandeur of this life. -- Camus

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.

If there is a sin against life, its consists perhaps not so much in despairing of life as in hoping for another life in eluding the implacable grandeur of this life. -- Camus

ceptimus
Posts: 1166
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: 1166
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: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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: 9999
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?

Cool Hand
....life purpose is pay taxes -- pillory 12/05/13

And you run and you run to catch up with the sun but it's sinking
Racing around to come up behind you again
The sun is the same in a relative way, but you're older
Shorter of breath and one day closer to death.

"Time" -- Pink Floyd

xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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.

xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building
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

Image courtesy of http://www.anatomorphex.com/FX013.html

DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
Yikes! This little puzzle has certainly expanded. And in some very interesting directions. Great stuff, xouper!

And Cool Hand, perhaps its time you picked up one of your dusty math books. (A little reading could help make you respectable despite your job. )