AOH :: PUZZLE03.FAQ
(3/15)
|
Article 3062 of news.answers:
Xref: news.UVic.CA rec.puzzles:11464 news.answers:3062
Newsgroups: rec.puzzles,news.answers
Path: news.UVic.CA!ubc-cs!destroyer!uunet!questrel!chris
From: uunet!questrel!chris (Chris Cole)
Subject: rec.puzzles FAQ, part 3 of 15
Message-ID: <puzzles-faq-3_717034101@questrel.com>
Followup-To: rec.puzzles
Summary: This posting contains a list of
Frequently Asked Questions (and their answers).
It should be read by anyone who wishes to
post to the rec.puzzles newsgroup.
Sender: chris@questrel.com (Chris Cole)
Reply-To: uunet!questrel!faql-comment
Organization: Questrel, Inc.
References: <puzzles-faq-1_717034101@questrel.com>
Date: Mon, 21 Sep 1992 00:08:46 GMT
Approved: news-answers-request@MIT.Edu
Expires: Sat, 3 Apr 1993 00:08:21 GMT
Lines: 1353
Archive-name: puzzles-faq/part03
Last-modified: 1992/09/20
Version: 3
==> arithmetic/digits/sesqui.s <==
Let's represent this number as a*10^n+b, where 1<=a<=9 and
b < 10^n. Then the condition to be satisfied is:
3/2(a*10^n+b) = 10b+a
3(a*10^n+b) = 20b+2a
3a*10^n+3b = 20b+2a
(3*10^n-2)a = 17b
b = a*(3*10^n-2)/17
So we must have 3*10^n-2 = 0 (mod 17) (since a is less than 10, it
cannot contribute the needed prime 17 to the factorization of 17b).
(Also, assuming large n, we must have a at most 5 so that b < 10^n will
be satisfied, but note that we can choose a=1). Now,
3*10^n-2 = 0 (mod 17)
3*10^n = 2 (mod 17)
10^n = 12 (mod 17)
A quick check shows that the smallest n which satisfies this is 15
(the fact that one exists was assured to us because 17 is prime). So,
setting n=15 and a=1 (obviously) gives us b=176470588235294, so the
number we are looking for is
1176470588235294
and, by the way, we can set a=2 to give us the second smallest such
number,
2352941176470588
Other things we can infer about these numbers is that there are 5 of
them less than 10^16, 5 more less than 10^33, etc.
==> arithmetic/digits/squares/leading.7.to.8.p <==
What is the smallest square with leading digit 7 which remains a square
when leading 7 is replaced by an 8?
==> arithmetic/digits/squares/leading.7.to.8.s <==
x=2996282391593370361328125
y=2824483699753370361328125
x^2=8977708170172487211329625006796419620513916015625
y^2=7977708170172487211329625006796419620513916015625
==> arithmetic/digits/squares/length.22.p <==
Is it possible to form two numbers A and B from 22 digits such that
A = B^2? Of course, leading digits must be non-zero.
==> arithmetic/digits/squares/length.22.s <==
No, the number of digits of A^2 must be of the form 3n or 3n-1.
==> arithmetic/digits/squares/length.9.p <==
Is it possible to make a number and its square, using the digits from 1 through
9 exactly once?
==> arithmetic/digits/squares/length.9.s <==
567 and 854.
==> arithmetic/digits/squares/three.digits.p <==
What squares consist entirely of three digits (e.g., 1, 4, and 9)?
==> arithmetic/digits/squares/three.digits.s <==
The full set of solutions up to 10**12 is
1 -> 1
2 -> 4
3 -> 9
7 -> 49
12 -> 144
21 -> 441
38 -> 1444
107 -> 11449
212 -> 44944
31488 -> 9914 94144
70107 -> 49149 91449
3 87288 -> 14 99919 94944
956 10729 -> 9 14141 14499 11441
4466 53271 -> 199 49914 44949 99441
31487 17107 -> 9914 41941 99144 49449
2 10810 79479 -> 4 44411 91199 99149 11441
If the algorithm is used in the form I presented it before, generating
the whole set P_n before starting on P_{n+1}, the store requirements
begin to become embarassing. For n>8 I switched to a depth-first
strategy, generating all the elements in P_i (i=9..12) congruent to
a particular x in P_8 for each x in turn. This means the solutions
don't come out in any particular order, of course. CPU time was 16.2
seconds (IBM 3084).
In article <1990Feb6.025205.28153@sun.soe.clarkson.edu>, Steven
Stadnicki suggests alternate triples of digits, in particular {1,4,6}
(with many solutions) and {2,4,8} (with few). I ran my program on
these as well, up to 10**12 again:
1 -> 1
2 -> 4
4 -> 16
8 -> 64
12 -> 144
21 -> 441
38 -> 1444
108 -> 11664
119 -> 14161
121 -> 14641
129 -> 16641
204 -> 41616
408 -> 1 66464
804 -> 6 46416
2538 -> 64 41444
3408 -> 116 14464
6642 -> 441 16164
12908 -> 1666 16464
25771 -> 6641 44441
78196 -> 61146 14416
81619 -> 66616 61161
3 33858 -> 11 14611 64164
2040 00408 -> 41 61616 64641 66464
6681 64962 -> 446 44441 64444 61444
8131 18358 -> 661 16146 41166 16164
40182 85038 -> 16146 61464 66146 61444 (Steven's last soln.)
1 20068 50738 -> 1 44164 46464 46111 44644
1 26941 38988 -> 1 61141 16464 66616 64144
1 27069 43631 -> 1 61466 41644 14114 64161
4 01822 24262 -> 16 14611 14664 16614 44644
4 05784 63021 -> 16 46611 66114 66644 46441
78 51539 12392 -> 6164 66666 14446 44111 61664
and
2 -> 4
22 -> 484
168 -> 28224
478 -> 2 28484
2878 -> 82 82884 (Steven's last soln.)
2109 12978 -> 44 48428 42888 28484
(so the answer to Steven's "Are there any more at all?" is "Yes".)
The CPU times were 42.9 seconds for {1,4,6}, 18.7 for {2,4,8}. This
corresponds to an interesting point: the abundance of solutions for
{1,4,6} is associated with abnormally large sets P_n (|P_8| = 16088
for {1,4,6} compared to |P_8| = 5904 for {1,4,9}) but the deficiency
of solutions for {2,4,8} is *not* associated with small P_n's (|P_8|
= 6816 for {2,4,8}). Can anyone wave a hand convincingly to explain
why the solutions for {2,4,8} are so sparse?
I suspect we are now getting to the point where an improved algorithm
is called for. The time to determine all the n-digit solutions (i.e.
2n-digit squares) using this last-significant-digit-first is essentially
constant * 3**n. Dean Hickerson in <90036.134503HUL@PSUVM.BITNET>, and
Ilan Vardi in <1990Feb5.214249.22811@Neon.Stanford.EDU>, suggest using
a most-significant-digit-first strategy, based on the fact that the
first n digits of the square determine the (integral) square root; this
also has a running time constant * 3**n. Can one attack both ends at
once and do better?
Chris Thompson
JANET: cet1@uk.ac.cam.phx
Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
Hey guys, what about
648070211589107021 ^ 2 = 419994999149149944149149944191494441
This was found by David Applegate and myself (about 5 minutes on a DEC 3100,
program in C).
This is the largest square less than 10^42 with the 149-property; checking
took a bit more than an hour of CPU time.
As somebody suggested, we used a combined most-significant/least-significant
digits attack. First we make a table of p-digit prefixes (most significant
p digits) that could begin a root whose square has the 149 property in its
first p digits. We organize this table into buckets by the least
significant q digits of the prefixes. Then we enumerate the s digit
suffixes whose squares have the 149 property in their last s digits. For
each such suffix, we look in the table for those prefixes whose last q
digits match the first q of the suffix. For each match, we consider the p +
s - q digit number formed by overlapping the prefix and the suffix by q
digits. The squares of these overlap numbers must contain all the squares
with the 149 property.
The time expended is O(3^p) to generate the prefix table, O(3^s) to
enumerate the suffixes, and O(3^(p+s) / 10^q) to check the overlaps (being
very rough and ignoring the polynomial factors) By judiciously chosing p, q,
and s, we can fix things so that each bucket of the table has around O(1)
entries: set q = p log10(3). Setting p = s, we end up looking for squares
whose roots have n = 2 - log10(3) digits, with an algorithm that takes time
O( 3 ^ [n / (2 - log10(3)]) ), roughly time O(3^[.66n]). Compared to the
O(3^n) performance of either single-ended algorithm, this lets us check 50%
more digits in the same amount of time (ignoring polynomial factors). Of
course, the space cost of the combined-ends method is high.
-- Guy and Dave
--
Guy Jacobson School of Computer Science
Carnegie Mellon arpanet : guy@cs.cmu.edu
Pittsburgh, PA 15213 csnet : Guy.Jacobson%a.cs.cmu.edu@csnet-relay
(412) 268-3056 uucp : ...!{seismo, ucbvax, harvard}!cs.cmu.edu!guy
Here is an algorithm which takes O(sqrt(n)log(n)) steps to find all perfect
squares < n whose only digits are 1, 4 and 9.
This doesn't sound too great *but* it doesn't use a lot of memory and only
requires addition and <. Also, the actual run time will depend on where the
first non-{1,4,9} digit appears in each square.
set n = 1
set odd = 1
while(n < MAXVAL)
{
if(all digits of n are in {1,4,9})
{
print n
}
add 2 to odd
add odd to n
}
This works because (X+1)^2 - x^2 = 2x+1.
That is, if you start with 0 and add successive odd
numbers to it you get 0+1=1, 1+3=4, 4+5=9, 9+7=16 etc.
I've started the algorithm at 1 for convenience.
The "O" value comes from looking at at most all digits
(log(n)) of all perfect squares < n (sqrt(n) of them)
at most a constant number of times.
I didn't save the articles with algorithms claiming to be
O(3^log(n)) so I don't know if their calculations needed
to (or did) account for multiplication or sqrt() of large
numbers. O(3^log(n)) sounds reasonable so I'm going to
assume they did unless I hear otherwise.
Any comments? Please email if you just want to refresh my memory
on the other algorithms.
Andrew Charles
acgd@ihuxy.ATT.COMM
==> arithmetic/digits/squares/twin.p <==
Let a twin be a number formed by writing the same number twice,
for instance, 81708170 or 132132. What is the smallest square twin?
==> arithmetic/digits/squares/twin.s <==
1322314049613223140496 = 36363636364 ^ 2.
The key to solving this puzzle is looking at the basic form of these
"twin" numbers, which is some number k = 1 + 10^n multiplied by some number
a < 10^n. If ak is a perfect square, k must have some repeated factor,
since a<k. Searching the possible values of k for one with a repeated factor
eventually turns up the number 1 + 10^11 = 11^2 * 826446281.
So, we set a=826446281 and ak = 9090909091^2 = 82644628100826446281,
but this needs leading zeros to fit the pattern. So, we multiply by a suitable
small square (in this case 16) to get the above answer.
==> arithmetic/digits/sum.of.digits.p <==
Find sod ( sod ( sod (4444 ^ 4444 ) ) ).
==> arithmetic/digits/sum.of.digits.s <==
let X = 4444^4444
sod(X) <= 9 * (# of digits) < 145900
sod(sod(X)) <= sod(99999) = 45
sod(sod(sod(X))) <= sod(39) = 12
but sod(sod(sod(X))) = 7 (mod 9)
thus sod(sod(sod(X))) = 7
==> arithmetic/digits/zeros/factorial.p <==
How many zeros are in the decimal expansion of n!?
==> arithmetic/digits/zeros/factorial.s <==
The general answer to the question
"what power of p divides x!" where p is prime
is (x-d)/(p-1) where d is the sum of the digits of (x written in base p).
So where p=5, 10 is written as 20 and is divisible by 5^2 (2 = (10-2)/4);
x to base 10: 100 1000 10000 100000 1000000
x to base 5: 400 13000 310000 11200000 224000000
d : 4 4 4 4 8
trailing 0s in x! 24 249 2499 24999 249998
==> arithmetic/digits/zeros/lsd.factorial.p <==
What is the least significant non-zero digit in the decimal expansion of n!?
==> arithmetic/digits/zeros/lsd.factorial.s <==
Reduce mod 10 the numbers 2..n and then cancel out the
required factors of 10. The final step then involves
computing 2^i*3^j*7^k mod 10 for suitable i,j and k.
A small program that performs this calculation is appended. Like the
other solutions, it takes O(log n) arithmetic operations.
-kym
===
#include<stdio.h>
#include<assert.h>
int p[6][4]={
/*2*/ 2, 4, 8, 6,
/*3*/ 3, 9, 7, 1,
/*4*/ 4, 6, 4, 6,
/*5*/ 5, 5, 5, 5,
/*6*/ 6, 6, 6, 6,
/*7*/ 7, 9, 3, 1,
};
main(){
int i;
int n;
for(n=2;n<1000;n++){
i=lsdfact(n);
printf("%d\n",i);
}
exit(0);
}
lsdfact(n){
int a[10];
int i;
int n5;
int tmp;
for(i=0;i<=9;i++)a[i]=alpha(i,n);
n5=0;
/* NOTE: order is important in following */
l5:;
while(tmp=a[5]){ /* cancel factors of 5 */
n5+=tmp;
a[1]+=(tmp+4)/5;
a[3]+=(tmp+3)/5;
a[5]=(tmp+2)/5;
a[7]+=(tmp+1)/5;
a[9]+=(tmp+0)/5;
}
l10:;
if(tmp=a[0]){
a[0]=0; /* cancel all factors of 10 */
for(i=0;i<=9;i++)a[i]+=alpha(i,tmp);
}
if(a[5]) goto l5;
if(a[0]) goto l10;
/* n5 == number of 5's cancelled;
must now cancel same number of factors of 2 */
i=ipow(2,a[2]+2*a[4]+a[6]+3*a[8]-n5)*
ipow(3,a[3]+a[6]+2*a[9])*
ipow(7,a[7]);
assert(i%10); /* must not be zero */
return i%10;
}
alpha(d,n){
/* number of decimal numbers in [1,n] ending in digit d */
int tmp;
tmp=(n+10-d)/10;
if(d==0)tmp--; /* forget 0 */
return tmp;
}
ipow(x,y){
/* x^y mod 10 */
if(y==0) return 1;
if(y==1) return x;
return p[x-2][(y-1)%4];
}
==> arithmetic/digits/zeros/million.p <==
How many zeros occur in the numbers from 1 to 1,000,000?
==> arithmetic/digits/zeros/million.s <==
In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)
numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of
which one tenth, or 9(n-1)10^(n-2), are zeroes. When we change the
range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in
10^n, gaining one zero, so
p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.
Solving the recurrence yields the closed form
p(n) = n(10^(n-1)+1) - (10^n-1)/9.
For n=6, there are 488,895 zeroes, 600,001 ones, and 600,000 of all other
digits.
==> arithmetic/magic.squares.p <==
Are there large squares, containing only consecutive integers, all of whose
rows, columns and diagonals have the same sum? How about cubes?
==> arithmetic/magic.squares.s <==
Here is an 8x8 example:
01 56 48 25 33 24 16 57
63 10 18 39 31 42 50 07
62 11 19 38 30 43 51 06
04 53 45 28 36 21 13 60
05 52 44 29 37 20 12 61
59 14 22 35 27 46 54 03
58 15 23 34 26 47 55 02
08 49 41 32 40 17 09 64
References:
"Magic Squares and Cubes"
W.S. Andrews
The Open Court Publishing Co.
Chicago, 1908
"Mathematical Recreations"
M. Kraitchik
Dover
New York, 1953
==> arithmetic/pell.p <==
Find integer solutions to x^2 - 92y^2 = 1.
==> arithmetic/pell.s <==
x=1 y=0
x=1151 y=120
x=2649601 y=276240
etc.
Each successive solution is about 2300 times the previous
solution; they are every 8th partial fraction (x=numerator,
y=denominator) of the continued fraction for sqrt(92) =
[9, 1,1,2,4,2,1,1,18, 1,1,2,4,2,1,1,18, 1,1,2,4,2,1,1,18, ...]
Once you have the smallest positive solution (x1,y1) you
don't need to "search" for the rest. You can obtain the nth positive
solution (xn,yn) by the formula
(x1 + y1 sqrt(92))^n = xn + yn sqrt(92).
See Niven & Zuckerman's An Introduction to the Theory of Numbers.
Look in the index under Pell's equation.
==> arithmetic/prime/arithmetic.progression.p <==
Is there an arithmetic progression of 20 or more primes?
==> arithmetic/prime/arithmetic.progression.s <==
There is an arithmetic progression of 21 primes:
142072321123 + 1419763024680 i, 0 <= i < 21.
It was discovered on 30 November 1990, by programs running in the background
on a network of Sun 3 workstations in the Department of Computer Science,
University of Queensland, Australia.
See: Andrew Moran and Paul Pritchard, The design of a background job
on a local area network, Procs. 14th Australian Computer Science Conference,
1991, to appear.
==> arithmetic/prime/consecutive.composites.p <==
Are there 10,000 consecutive non-prime numbers?
==> arithmetic/prime/consecutive.composites.s <==
9973!+2 through 9973!+10006 are composite.
==> arithmetic/sequence.p <==
Prove that all sets of n integers contain a subset whose sum is divisible by n.
==> arithmetic/sequence.s <==
Consider the set of remainders of the partial sums a(1) + ... + a(i).
Since there are n such sums, either one has remainder zero (and we're
thru) or 2 coincide, say the i'th and j'th. In this case, a(i+1) +
... + a(j) is divisible by n. (note this is a stronger result since
the subsequence constructed is of *adjacent* terms.) Consider a(1)
(mod n), a(1)+a(2) (mod n), ..., a(1)+...+a(n) (mod n). Either at
some point we have a(1)+...+a(m) = 0 (mod n) or else by the pigeonhole
principle some value (mod n) will have been duplicated. We win either
way.
==> arithmetic/sum.of.cubes.p <==
Find two fractions whose cubes total 6.
==> arithmetic/sum.of.cubes.s <==
Restated:
Find X, Y, minimum Z (all positive integers) where
(X/Z)^3 + (Y/Z)^3 = 6
Again, a generalized solution would be nice.
You are asking for the smallest z s.t. x^3 + y^3 = 6*z^3 and x,y,z in Z+.
In general, questions like these are extremely difficult; if you're
interested take a look at books covering Diophantine equations
(especially Baker's work on effective methods of computing solutions).
Dudeney mentions this problem in connection with #20 in _The Canterbury
Puzzles_; the smallest answer is (17/21)^3 + (37/21)^3 = 6.
For the interest of the readers of this group I'll quote:
"Given a known case for the expression of a number as the sum or
difference of two cubes, we can, by formula, derive from it an infinite
number of other cases alternately positive and negative. Thus Fermat,
starting from the known case 1^3 + 2^3 = 9 (which we will call a
fundamental case), first obtained a negative solution in bigger
figures, and from this his positive solution in bigger figures still.
But there is an infinite number of fundamentals, and I found by trial
a negative fundamental solution in smaller figures than his derived
negative solution, from which I obtained the result shown above. That
is the simple explanation."
In the above paragraph Dudeney is explaining how he derived (*by hand*)
that (415280564497/348671682660)^3 + (676702467503/348671682660)^3 = 9.
He continues:
"We can say of any number up to 100 whether it is possible or not to
express it as the sum of two cubes, except 66. Students should read
the Introduction to Lucas's _Theorie des Nombres_, p. xxx."
"Some years ago I published a solution for the case 6 = (17/21)^3 +
(37/21)^3, of which Legendre gave at some length a 'proof' of
impossibility; but I have since found that Lucas anticipated me in
a communication to Sylvester."
==> arithmetic/tests.for.divisibility/eleven.p <==
What is the test to see if a number is divisible by eleven?
==> arithmetic/tests.for.divisibility/eleven.s <==
If the alternating sum of the digits is divisible by eleven, so is the number.
For example, 1639 leads to 9 - 3 + 6 - 1 = 11, so 1639 is divisible by 11.
Proof:
Every integer n can be expressed as
n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
10 is congruent to -1 mod(11).
Thus if (-1^k)*a1 + (-1^k-1)*a2 + ...+ (a_k+1) is congruent to 0mod(11) then
n is divisible by 11.
==> arithmetic/tests.for.divisibility/nine.p <==
What is the test to see if a number is divisible by nine?
==> arithmetic/tests.for.divisibility/nine.s <==
If the sum of the digits is divisible by nine, so is the number.
Proof:
Every integer n can be expressed as
n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
Note that 10 is congruent to 1 (mod 9). Thus 10^k is congruent to 1 (mod 9) for
every k >= 0.
Thus n is congruent to (a1+a2+a3+....+a_k+1) mod(9).
Hence (a1+a2+...+a_k+1) is divisible by 9 iff n is divisible by 9.
==> arithmetic/tests.for.divisibility/seven.p <==
What is the test to see if a number is divisible by 7?
==> arithmetic/tests.for.divisibility/seven.s <==
Take the last digit (n mod 10) and double it.
Take the rest of the digits (n div 10) and subtract the doubled last
digit from it.
The resulting number is divisible by 7 iff the original number
is divisible by 7.
Example: Take 2009.
Subtract (2009 mod 10) * 2 from (2009 div 10)
- 9 * 2 + 200
= 182
Subtract (182 mod 10) * 2 from (182 div 10)
- 2 * 2 + 18
= 14
so 2009 is divisible by 7.
==> arithmetic/tests.for.divisibility/three.p <==
Prove that if a number is divisible by 3, the sum of its digits is likewise.
==> arithmetic/tests.for.divisibility/three.s <==
First, prove 10^N = 1 mod 3 for all integers N >= 0.
1 = 1 mod 3. 10 = 1 mod 3. 10^N = 10^(N-1) * 10 = 10^(N-1) mod 3.
QED by induction.
Now let D[0] be the units digit of N, D[1] the tens digit, etc.
Now N = Summation From k=0 to k=inf of D[k]*10^k.
Therefore N mod 3 = Summation from k=0 to k=inf of D[k] mod 3. QED
==> combinatorics/coinage/combinations.p <==
How many ways are there to make change for a dollar? Count
combinations of coins, not permuations.
==> combinatorics/coinage/combinations.s <==
Assuming that you had coins of one cent, five cents, ten cents, 25 cents,
50 cents, and 100 cents, there are 293 ways to make change for a dollar.
This can be calculated by determining the number of ways to make change
using only a penny and then a penny and nickel, then penny, nickel, and
dime, etc.
The table is shown below:
Amount 00 05 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Coins
.01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
.05 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
.10 1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 90 100 110 121
.25 1 2 4 6 9 13 18 24 31 39 49 60 73 87 103 121 141 163 187 214 242
.50 1 2 4 6 9 13 18 24 31 39 49 62 77 93 112 134 159 187 218 253 292
1.0 1 2 4 6 9 13 18 24 31 39 49 62 77 93 112 134 159 187 218 253 293
The meaning of each entry is as follows:
If you wish to make change for 50 cents using only pennies, nickels and dimes,
go to the .10 row and the 50 column to obtain 36 ways to do this.
To calculate each entry, you start with the pennies. There is exactly one
way to make change for every amount. Then calculate the .05 row by adding
the number of ways to make change for the amount using pennies plus the number
of ways to make change for five cents less using nickels and pennies. This
continues on for all denominations of coins.
An example, to get change for 75 cents using all coins up to a .50, add the
number of ways to make change using only .25 and down (121) and the number of
ways to make change for 25 cents using coins up to .50 (13). This yields the
answer of 134.
==> combinatorics/coinage/dimes.p <==
"Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent
stamps. He said to get four each of two sorts and three each of the
others, but I've forgotten which. He gave me exactly enough to buy
them; just these dimes." How many stamps of each type does Dad want?
[J.A.H. Hunter]
==> combinatorics/coinage/dimes.s <==
The easy way to solve this is to sell her three each, for
3x(1+2+3+5+10) = 63 cents. Two more stamps must be bought, and they
must make seven cents (since 17 is too much), so the fourth stamps are
a two and a five.
==> combinatorics/coinage/impossible.p <==
What is the smallest number of coins that you can't make a dollar with?
I.e., for what N does there not exist a set of N coins adding up to a dollar?
It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),
2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece),
etc. It is not possible to make exactly a dollar with 101 coins.
==> combinatorics/coinage/impossible.s <==
The answer is 77:
a) 5c = 1 or 5;
b) 10c = 1 or 2 a's (1,2,6,10)
c) 25c = 1 or 2 b's + 1 a
d) 50c = 1 or 2 c's
e) $1 = 1 or 2 d's
total penny nickle dime quarter half
5 1 2 1 1
6 3 1 1 1
7 5 1 1
8 4 3 1
9 6 2 1
10 8 1 1
11 10 1
12 7 4 1
13 9 3 1
14 11 2 1
15 13 1 1
16 15 1
17 14 3
18 16 2
19 18 1
20 20
21 5 13 3
22 5 15 2
23 5 17 1
24 5 19
25 10 12 3
26 10 14 2
27 10 16 1
28 10 18
29 15 11 3
30 15 13 2
31 15 15 1
32 15 17
33 20 10 3
34 20 12 2
35 20 14 1
36 20 16
37 25 9 3
38 25 11 2
39 25 13 1
40 25 15
41 30 8 3
42 30 10 2
43 30 12 1
44 30 14
45 35 7 3
46 35 9 2
47 35 11 1
48 35 13
49 40 6 3
50 40 8 2
51 40 10 1
52 40 12
53 45 5 3
54 45 7 2
55 45 9 1
56 45 11
57 50 4 3
58 50 6 2
59 50 8 1
60 50 10
61 55 3 3
62 55 5 2
63 55 7 1
64 55 9
65 60 2 3
66 60 4 2
67 60 6 1
68 60 8
69 65 1 3
70 65 3 2
71 65 5 1
72 65 7
73 70 3
74 70 2 2
75 70 4 1
76 70 6
77 can't be done
78 75 1 2
79 75 3 1
80 75 5
81 can't be done
82 80 2
83 80 2 1
84 80 4
85 can't be done
86 can't be done
87 85 1 1
88 85 3
89 can't be done
90 can't be done
91 90 1
92 90 2
93-95 can't be done
96 95 1
97-99 can't be done
100 100
==> combinatorics/color.p <==
An urn contains n balls of different colors. Randomly select a pair, repaint
the first to match the second, and replace the pair in the urn. What is the
expected time until the balls are all the same color?
==> combinatorics/color.s <==
(n-1)^2.
If the color classes have sizes k1, k2, ..., km, then the expected number of
steps from here is (dropping the subscript on k):
2 k(k-1) (j-1) (k-j)
(n-1) - SUM ( ------ + SUM --------------- )
classes, 2 1<j<k (n-j)
class.size=k
The verification goes roughly as follows. Defining phi(k) as (k(k-1)/2 +
sum[j]...), we first show that phi(k+1) + phi(k-1) - 2*phi(k) = (n-1)/(n-k)
except when k=n; the k(k-1)/2 contributes 1, the term j=k contributes
(j-1)/(n-j)=(k-1)/(n-k), and the other summands j<k contribute nothing.
Then we say that the expected change in phi(k) on a given color class is
k*(n-k)/(n*(n-1)) times (phi(k+1) + phi(k-1) - 2*phi(k)), since with
probability k*(n-k)/(n*(n-1)) the class goes to size k+1 and with the same
probability it goes to size k-1. This expected change comes out to k/n.
Summing over the color classes (and remembering the minus sign), the
expected change in the "cost from here" on one step is -1, except when we're
already monochromatic, where the handy exception k=n kicks in.
One can rewrite the contribution from k as
(n-1) SUM (k-j)/(n-j)
0<j<k
which incorporates both the k(k-1)/2 and the previous sum over j.
That makes the proof a little cleaner.
==> combinatorics/full.p <==
Consider a string that contains all substrings of length n. For example,
for binary strings with n=2, a shortest string is 00110 -- it contains 00,
01, 10 and 11 as substrings. Find the shortest such strings for all n.
==> combinatorics/full.s <==
Knuth, Volume 2 Seminumerical Algorithms, section 3.2.2 discusses this problem.
He cites the following results:
Shortest length: m^n + n - 1, where m = number of symbols in the language.
Algorithms:
[Exercise 7, W. Mantel, 1897]
The binary sequence is the LSB of X computed by the MIX program:
LDA X
JANZ *+2
LDA A
ADD X
JNOV *+3
JAZ *+2
XOR A
STA X
[Exercise 10, M. H. Martin, 1934]
Set x[1] = x[2] = ... = x[n] = 0. Set x[i+1] = largest value < n such that
substring of n digits ending at x[i+1] does not occur earlier in string.
Terminate when this is not possible.
If we instead consider the strings as circular, we have a well known
problem whose solution is given by any hamiltonian cycle in the de
Bruijn (or Good) graph of dimension K. (Or equivalently an eulerian
circuit in the de Bruijn graph of dimension K-1) As a string of length
2^K is produced, it must be optimal, and any shortest sequence must be
an eulerian circuit in a dB graph.
The de Bruijn graph Tn has as its vertex set the binary n-strings.
Directed edges join n-strings that may be derived by deleting the left
most digit and appending a 0 or 1 to the right end. de Bruijn + van
Ardenne-Ehrenfest (in 1951) counted the number of eulerian circuits in
Tn. There are 2^(2^(n-1)-n) of them.
Some examples:
K=2 1100
K=3 11101000
K=4 1111001011010000
The solution to the above problem (non-circular strings) can be found
by duplicating the first K-1 digits of the solution string at the end
of the string. These are not the only solutions, but they
are of minimum length: 2^K + K-1.
We can obtain a lower bound for the optimal sequence for the general case as
follows:
Consider first the simpler case of breaking into an answer machine which
accepts d+1 digits, values 0 to n-1. We wish to find the minimal universal
code that will allow us access to any such answering machine.
Let us construct a digraph G = (V,E), where the n^d vertices are labelled
with a d sequence of digits. Notation: let [v_{i,1},v_{i,2},...,v_{i,d}]
denote the labelling on node v_i. An edge e = (v_i, v_j) is in E iff for k
in 1, ..., d-1: v_{i,k+1} = v_{j,k}, i.e., the last d-1 digits in the
labelling of the initial vertex of e is identical with the first d-1 digits
in the labelling of the terminal vertex of e. We associate with each edge a
value, t(e) = v_{j,d}, the last digit in the labelling of the terminal
vertex.
The intuition goes as follows: we are going to perform a Euler circuit of
the digraph, where the label on the current vertex gives the last d digits
in the output sequence so far. If we make a transition on edge e, we output
the tone/digit t(e) as the next output value, thus preserving the invariant
on the labelling.
How do we know that a Euler circuit exists? Simple: a connected digraph
has an Euler circuit iff for all vertices v: indegree(v) = outdegree(v).
This property is trivially true for this digraph.
So, in order to generate a universal code for the AM, we simply output 0^d
(to satisfy the precondition for being in vertex [0,...,0]), and perform an
Euler circuit starting at node [0,...,0].
Now, the total length of the universal sequence is just the number of edges
traversed in the Euler circuit plus the initial precondition sequence, or
n^d * n + d (number of vertices times the out-degree) or n^{d+1} + d. That
this is a minimal sequence is obvious.
Next, let us consider the machine AM' where the security code is of the form
[0...n-1]^d [0...m-1], i.e., d digits ranging from 0 to n-1, followed by a
terminal digit ranging from 0 to m-1, m < n.
We build a digraph G = (V, E) similar to the construction above, except for
the following: an edge e is in E iff t(e) in 0 to m-1. This digraph is
clearly non-Eulerian. In particular, there are two classes of vertices:
(1) v is of the form [0...n-1]^{d-1} [0...m-1] (``fat'' vertices)
and
(2) v is of the form [0...n-1]^{d-1} [m...n-1] (``thin'' vertices)
Observations: there are (n^{d-1} * m) fat vertices, and (n^{d-1} * (n-m))
thin vertices. All vertices have out-degree of m. Fat vertices have
in-degrees of n, and thin vertices have in-degrees of 0. Color all the
edges blue.
The question now becomes: can we put a bound on how many new (red) edges
must we add to G in order to make a blue edge covering path possible?
(Instead of thinking of edges being traversed multiple times in the blue
edge covering path, we allow multiple edges between vertices and allow each
edge to be traversed once.) Note that, in this procedure, we add edges only
if it is allowed (the vertex labelling constraint). We will first obtain a
lower bound on the length of a blue covering circuit, and then transform it
into a bound for arbitrary blue covering paths.
Clearly, we must add at least (n-m)*(n^{d-1}*m) edges incident from the fat
vertices. [ We need (n-m) new out-going edges for each of (n^{d-1}*m)
vertices to bring the out-degree up to the in-degree. ]
Let us partition our vertices into sets. Denote the range [0..m-1] by S,
the range [m..n-1] by L, and the range [0..n-1] by X.
Let S_0 = { v: v = [X^{d-1}S] }. S_0 is just the set of fat vertices.
Define in(S_0) = number of edges from vertices not in S to vertices in S.
Define out(S_0) in the corresponding fashion, and let excess(S_0) =
in(S_0)-out(S_0). Clearly, excess(S_0) = n^{d-1}m(n-m) from the argument
above. Generalizing the requirement for Eulerian digraphs, we see that we
must add excess(S_0) edges from S_0 if the blue edges connected to/within
S_0 are to be covered by some circuit (edges may not be travered multiple
times -- we add parallel edges to handle that case). In particular, edges
from S_0 will be incident on vertices of the form [X^{d-2}SX]. Furthermore,
they can not be [X^{d-2}SS] since that is a subset of S_0 and adding those
edges will not help excess(S_0). [Now, these edges may be needed if we are
to have a circuit, but we do not consider them since they do not help
excess(S_0).] So, we are forced to add excess(S_0) edges from S_0 to S_1 = {
v: v = [X^{d-2}SL] }. Color these newly added edges red.
Let us define in(S_1), out(S_1) and excess(S_1) as above for the modified
digraph, i.e., including the red excess(S_0) edges that we just added.
Clearly, in(S_1) = out(S_0) = n^{d-1}m(n-m), and out(S_1) = m*|S_1| =
m*n^{d-2}m(n-m), so excess(S_1) = n^{d-2}m(n-m)^2. Consider S_0 union S_1.
We must add excess(S_1) edges to S_0 union S_1 to make it possible for the
digraph to be covered by a circuit, and these edges must go from {S_0 union
S_1} to S_2 = { v: v = [X^{d-3}SL^2] } by a similar argument as before.
Repeating this partitioning process, eventually we get to S_{d-1} = { v: v =
[SL^{d-1}] }, where union of S_0 to S_{d-1} will need edges to S_d = { v: v
= [L^d] }, where this process terminates. Note that at this time,
excess(union of S_0 to S_{d-1}) = m(n-m)^d, but in(S_d) = 0 and out(S_d) =
m(n-m)^d, and the process terminates.
What have we shown? Adding up blue edges and the red edges gives us a lower
bound on the total number of edges in a blue-edges covering circuit (not
necessarily Eulerian) in the complete digraph. This comes out to be
n^{d+1}-(n-m)^{d+1} edges.
Next, we note that if we had an optimal path covering all the blue edges, we
can transform it into a circuit by adding d edges. So, a minimal path can
be no more than d edges shorter than the minimal circuit covering all blue
edges. [Otherwise, we add d extra edges to make it into a shorter circuit.]
So the shortest blue covering path through the digraph is at least
n^{d+1}-{n-m}^{d+1}-d. With an initial pre-condition sequence of length d
(to establish the transition invariant), the shortest universal answering
machine sequence is of length at least n^{d+1}-(n-m)^{d+1}.
While this has not been that constructive, it is easy to see that we can
achieve this bound. If we looked at the vertices in each of the S_i's, we
just add exactly the edges to S_{i+1} and no more. The resultant digraph
would be Eulerian, and to find the minimal path we need only start at the
vertex labelled [{n-1}^d], find the Euler circuit, and omit the last d edges
from the tour.
==> combinatorics/gossip.p <==
n people each know a different piece of gossip. They can telephone each other
and exchange all the information they know (so that after the call they both
know anything that either of them knew before the call). What is the smallest
number of calls needed so that everyone knows everything?
==> combinatorics/gossip.s <==
1 for n=2
3 for n=3
2n-4 for n>=4
This can be achieved as follows: choose four professors (A, B, C, and D) as
the "core group". Each professor outside the core group phones a member of
the core group (it doesn't matter which); this takes n-4 calls. Now the
core group makes 4 calls: A-B, C-D, A-C, and B-D. At this point, each
member of the core group knows everything. Now, each person outside the
core group calls anybody who knows everything; this again requires n-4
calls, for a total of 2n-4.
The solution to the "gossip problem" has been published several times:
1. R. Tidjeman, "On a telephone problem", Nieuw Arch. Wisk. 3
(1971), 188-192.
2. B. Baker and R. Shostak, "Gossips and telephones", Discrete
Math. 2 (1972), 191-193.
3. A. Hajnal, E. C. Milner, and E. Szemeredi, "A cure for the
telephone disease", Canad Math. Bull 15 (1976), 447-450.
4. Kleitman and Shearer, Disc. Math. 30 (1980), 151-156.
5. R. T. Bumby, "A problem with telephones", Siam J. Disc. Meth. 2
(1981), 13-18.
==> combinatorics/grid.dissection.p <==
How many (possibly overlapping) squares are in an mxn grid?
==> combinatorics/grid.dissection.s <==
Given an n*m grid with n > m.
Orient the grid so n is its width. Divide the grid into two portions,
an m*m square on the left and an (n-m)*m rectangle on the right.
Count the squares that have their upper right-hand corners in the
m*m square. There are m^2 of size 1*1, (m-1)^2 of size 2*2, ...
up to 1^2 of size m*m. Now look at the n-m columns of lattice points
in the rectangle on the right, in which we find upper right-hand
corners of squares not yet counted. For each column we count m new
1*1 squares, m-1 new 2*2 squares, ... up to 1 new m*m square.
Combining all these counts in summations:
m m
total = sum i^2 + (n - m) sum i
i=1 i=1
(2m + 1)(m + 1)m (n - m)(m + 1)m
= ---------------- + ---------------
6 2
= (3n - m + 1)(m + 1)m/6
-- David Karr
==> combinatorics/subsets.p <==
Out of the set of integers 1,...,100 you are given ten different
integers. From this set, A, of ten integers you can always find two
disjoint subsets, S & T, such that the sum of elements in S equals the
sum of elements in T. Note: S union T need not be all ten elements of
A. Prove this.
==> combinatorics/subsets.s <==
First, a couple of points:
(1) All empty subsets of the 10 integers are disjoint and have the same sum.
This doesn't make for a very interesting problem. Thus, we impose the
additional restriction that S and T be non-empty.
(2) The 10 integers must be pairwise distinct. Consider, e.g., the 10
integers 1, 1, 1, 1, 1, 1, 1, 1, 1, and 1. There are no non-empty
disjoint subsets with equal sums.
Proof of puzzle:
There are 2^10 = 1,024 subsets of the 10 integers, but there can be only 901
possible sums, the number of integers between the minimum and maximum sums.
With more subsets than possible sums, there must exist at least one sum that
corresponds to at least two subsets. Call two subsets with equal sums A and B.
Let C = A intersect B; define S = A - C, T = B - C. Then S is disjoint from T,
and sum(S) = sum(A-C) = sum(A) - sub(C) = sum(B) - sum(C) = sum(B-C) = sum(T).
QED
==> cryptology/Beale.p <==
What are the Beale ciphers?
==> cryptology/Beale.s <==
The Beale ciphers are one of the greatest unsolved puzzles of all time.
About 100 years ago, a fellow by the name of Beale supposedly buried two
wagons-full of silver-coin filled pots in Bedford County, near Roanoke.
There are local rumors about the treasure being buried near Bedford Lake.
He wrote three encoded letters telling what was buried, where it was buried,
and who it belonged to. He entrusted these three letters to a friend and went
west. He was never heard from again.
Several years later, someone examined the letters and was able to break the
code used in the second letter. The code used either the text from the
Declaration of Independence. A number in the letter indicated which word
in the document was to be used. The first letter of that word replaced the
number. For example, if the first three words of the document were "We
hold these truths", the number 3 in the letter would represent the letter t.
One of the remaining letters supposedly contains directions on how to find
the treasure. To date, no one has solved the code. It is believed that
both of the remaining letters are encoded using either the same document
in a different way, or another very public document.
For those interested, write to:
The Beale Cypher Association
P.O. Box 975
Beaver Falls, PA 15010
Item #904 is the 1885 pamphlet version ($5.00). #152 is the
Cryptologia article by Gillogly that argues the hoax side ($2.00).
A year's membership is $25, and includes 4 newsletters.
TEXT for part 1
The Locality of the Vault.
71,194,38,1701,89,76,11,83,1629,48,94,63,132,16,111,95,84,341
975,14,40,64,27,81,139,213,63,90,1120,8,15,3,126,2018,40,74
758,485,604,230,436,664,582,150,251,284,308,231,124,211,486,225
401,370,11,101,305,139,189,17,33,88,208,193,145,1,94,73,416
918,263,28,500,538,356,117,136,219,27,176,130,10,460,25,485,18
436,65,84,200,283,118,320,138,36,416,280,15,71,224,961,44,16,401
39,88,61,304,12,21,24,283,134,92,63,246,486,682,7,219,184,360,780
18,64,463,474,131,160,79,73,440,95,18,64,581,34,69,128,367,460,17
81,12,103,820,62,110,97,103,862,70,60,1317,471,540,208,121,890
346,36,150,59,568,614,13,120,63,219,812,2160,1780,99,35,18,21,136
872,15,28,170,88,4,30,44,112,18,147,436,195,320,37,122,113,6,140
8,120,305,42,58,461,44,106,301,13,408,680,93,86,116,530,82,568,9
102,38,416,89,71,216,728,965,818,2,38,121,195,14,326,148,234,18
55,131,234,361,824,5,81,623,48,961,19,26,33,10,1101,365,92,88,181
275,346,201,206,86,36,219,324,829,840,64,326,19,48,122,85,216,284
919,861,326,985,233,64,68,232,431,960,50,29,81,216,321,603,14,612
81,360,36,51,62,194,78,60,200,314,676,112,4,28,18,61,136,247,819
921,1060,464,895,10,6,66,119,38,41,49,602,423,962,302,294,875,78
14,23,111,109,62,31,501,823,216,280,34,24,150,1000,162,286,19,21
17,340,19,242,31,86,234,140,607,115,33,191,67,104,86,52,88,16,80
121,67,95,122,216,548,96,11,201,77,364,218,65,667,890,236,154,211
10,98,34,119,56,216,119,71,218,1164,1496,1817,51,39,210,36,3,19
540,232,22,141,617,84,290,80,46,207,411,150,29,38,46,172,85,194
39,261,543,897,624,18,212,416,127,931,19,4,63,96,12,101,418,16,140
230,460,538,19,27,88,612,1431,90,716,275,74,83,11,426,89,72,84
1300,1706,814,221,132,40,102,34,868,975,1101,84,16,79,23,16,81,122
324,403,912,227,936,447,55,86,34,43,212,107,96,314,264,1065,323
428,601,203,124,95,216,814,2906,654,820,2,301,112,176,213,71,87,96
202,35,10,2,41,17,84,221,736,820,214,11,60,760
TEXT for part 2
(no title exists for this part)
115,73,24,807,37,52,49,17,31,62,647,22,7,15,140,47,29,107,79,84
56,239,10,26,811,5,196,308,85,52,160,136,59,211,36,9,46,316,554
122,106,95,53,58,2,42,7,35,122,53,31,82,77,250,196,56,96,118,71
140,287,28,353,37,1005,65,147,807,24,3,8,12,47,43,59,807,45,316
101,41,78,154,1005,122,138,191,16,77,49,102,57,72,34,73,85,35,371
59,196,81,92,191,106,273,60,394,620,270,220,106,388,287,63,3,6
191,122,43,234,400,106,290,314,47,48,81,96,26,115,92,158,191,110
77,85,197,46,10,113,140,353,48,120,106,2,607,61,420,811,29,125,14
20,37,105,28,248,16,159,7,35,19,301,125,110,486,287,98,117,511,62
51,220,37,113,140,807,138,540,8,44,287,388,117,18,79,344,34,20,59
511,548,107,603,220,7,66,154,41,20,50,6,575,122,154,248,110,61,52,33
30,5,38,8,14,84,57,540,217,115,71,29,84,63,43,131,29,138,47,73,239
540,52,53,79,118,51,44,63,196,12,239,112,3,49,79,353,105,56,371,557
211,505,125,360,133,143,101,15,284,540,252,14,205,140,344,26,811,138
115,48,73,34,205,316,607,63,220,7,52,150,44,52,16,40,37,158,807,37
121,12,95,10,15,35,12,131,62,115,102,807,49,53,135,138,30,31,62,67,41
85,63,10,106,807,138,8,113,20,32,33,37,353,287,140,47,85,50,37,49,47
64,6,7,71,33,4,43,47,63,1,27,600,208,230,15,191,246,85,94,511,2,270
20,39,7,33,44,22,40,7,10,3,811,106,44,486,230,353,211,200,31,10,38
140,297,61,603,320,302,666,287,2,44,33,32,511,548,10,6,250,557,246
53,37,52,83,47,320,38,33,807,7,44,30,31,250,10,15,35,106,160,113,31
102,406,230,540,320,29,66,33,101,807,138,301,316,353,320,220,37,52
28,540,320,33,8,48,107,50,811,7,2,113,73,16,125,11,110,67,102,807,33
59,81,158,38,43,581,138,19,85,400,38,43,77,14,27,8,47,138,63,140,44
35,22,177,106,250,314,217,2,10,7,1005,4,20,25,44,48,7,26,46,110,230
807,191,34,112,147,44,110,121,125,96,41,51,50,140,56,47,152,540
63,807,28,42,250,138,582,98,643,32,107,140,112,26,85,138,540,53,20
125,371,38,36,10,52,118,136,102,420,150,112,71,14,20,7,24,18,12,807
37,67,110,62,33,21,95,220,511,102,811,30,83,84,305,620,15,2,108,220
106,353,105,106,60,275,72,8,50,205,185,112,125,540,65,106,807,188,96,110
16,73,32,807,150,409,400,50,154,285,96,106,316,270,205,101,811,400,8
44,37,52,40,241,34,205,38,16,46,47,85,24,44,15,64,73,138,807,85,78,110
33,420,505,53,37,38,22,31,10,110,106,101,140,15,38,3,5,44,7,98,287
135,150,96,33,84,125,807,191,96,511,118,440,370,643,466,106,41,107
603,220,275,30,150,105,49,53,287,250,208,134,7,53,12,47,85,63,138,110
21,112,140,485,486,505,14,73,84,575,1005,150,200,16,42,5,4,25,42
8,16,811,125,160,32,205,603,807,81,96,405,41,600,136,14,20,28,26
353,302,246,8,131,160,140,84,440,42,16,811,40,67,101,102,194,138
205,51,63,241,540,122,8,10,63,140,47,48,140,288
CLEAR for part 2, made human readable.
I have deposited in the county of Bedford about four miles from
Bufords in an excavation or vault six feet below the surface
of the ground the following articles belonging jointly to
the parties whose names are given in number three herewith.
The first deposit consisted of ten hundred and fourteen pounds
of gold and thirty eight hundred and twelve pounds of silver
deposited Nov eighteen nineteen. The second was made Dec
eighteen twenty one and consisted of nineteen hundred and seven
pounds of gold and twelve hundred and eighty eight of silver,
also jewels obtained in St. Louis in exchange to save transportation
and valued at thirteen [t]housand dollars. The above
is securely packed i[n] [i]ron pots with iron cov[e]rs. Th[e] vault
is roughly lined with stone and the vessels rest on solid stone
and are covered [w]ith others. Paper number one describes th[e]
exact locality of the va[u]lt so that no difficulty will be had
in finding it.
CLEAR for part 2, using only the first 480 words of the
Declaration of Independence, then blanks filled in by
inspection. ALL mistakes shown were caused by sloppy
encryption.
0----5----10---15---20---25---30---35---40---45---
0 ihavedepositedinthecountyofbedfordaboutfourmilesfr
50 ombufordsinanexcavationorvaultsixfeetbelowthesurfa
100 ceofthegroundthefollowingarticlesbelongingjointlyt
150 othepartieswhosenamesaregiveninnumberthreeherewith
200 thefirstdepositconsistcdoftenhundredandfourteenpou
250 ndsofgoldandthirtyeighthundredandtwelvepoundsofsil
300 verdepositednoveighteennineteenthesecondwasmadedec
350 eighteentwentyoneandconsistedofnineteenhundredands
400 evenpoundsofgoldandtwelvehundredandeightyeightofsi
450 lveralsojewelsobtainedinstlouisinexchangetosavetra
500 nsportationandvaluedatthirteenrhousanddollarstheab
550 oveissecurelypackeditronpotswithironcovtrsthtvault
600 isroughlylinedwithstoneandthevesselsrestonsolidsto
650 neandarecovereduithotherspapernumberonedescribesth
700 cexactlocalityofthevarltsothatnodifficultywillbeha
750 dinfindingit
TEXT for part 3
Names and Residences.
317,8,92,73,112,89,67,318,28,96,107,41,631,78,146,397,118,98
114,246,348,116,74,88,12,65,32,14,81,19,76,121,216,85,33,66,15
108,68,77,43,24,122,96,117,36,211,301,15,44,11,46,89,18,136,68
317,28,90,82,304,71,43,221,198,176,310,319,81,99,264,380,56,37
319,2,44,53,28,44,75,98,102,37,85,107,117,64,88,136,48,154,99,175
89,315,326,78,96,214,218,311,43,89,51,90,75,128,96,33,28,103,84
65,26,41,246,84,270,98,116,32,59,74,66,69,240,15,8,121,20,77,80
31,11,106,81,191,224,328,18,75,52,82,117,201,39,23,217,27,21,84
35,54,109,128,49,77,88,1,81,217,64,55,83,116,251,269,311,96,54,32
120,18,132,102,219,211,84,150,219,275,312,64,10,106,87,75,47,21
29,37,81,44,18,126,115,132,160,181,203,76,81,299,314,337,351,96,11
28,97,318,238,106,24,93,3,19,17,26,60,73,88,14,126,138,234,286
297,321,365,264,19,22,84,56,107,98,123,111,214,136,7,33,45,40,13
28,46,42,107,196,227,344,198,203,247,116,19,8,212,230,31,6,328
65,48,52,59,41,122,33,117,11,18,25,71,36,45,83,76,89,92,31,65,70
83,96,27,33,44,50,61,24,112,136,149,176,180,194,143,171,205,296
87,12,44,51,89,98,34,41,208,173,66,9,35,16,95,8,113,175,90,56
203,19,177,183,206,157,200,218,260,291,305,618,951,320,18,124,78
65,19,32,124,48,53,57,84,96,207,244,66,82,119,71,11,86,77,213,54
82,316,245,303,86,97,106,212,18,37,15,81,89,16,7,81,39,96,14,43
216,118,29,55,109,136,172,213,64,8,227,304,611,221,364,819,375
128,296,1,18,53,76,10,15,23,19,71,84,120,134,66,73,89,96,230,48
77,26,101,127,936,218,439,178,171,61,226,313,215,102,18,167,262
114,218,66,59,48,27,19,13,82,48,162,119,34,127,139,34,128,129,74
63,120,11,54,61,73,92,180,66,75,101,124,265,89,96,126,274,896,917
434,461,235,890,312,413,328,381,96,105,217,66,118,22,77,64,42,12
7,55,24,83,67,97,109,121,135,181,203,219,228,256,21,34,77,319,374
382,675,684,717,864,203,4,18,92,16,63,82,22,46,55,69,74,112,134
186,175,119,213,416,312,343,264,119,186,218,343,417,845,951,124
209,49,617,856,924,936,72,19,28,11,35,42,40,66,85,94,112,65,82
115,119,233,244,186,172,112,85,6,56,38,44,85,72,32,47,63,96,124
217,314,319,221,644,817,821,934,922,416,975,10,22,18,46,137,181
101,39,86,103,116,138,164,212,218,296,815,380,412,460,495,675,820
952
Evidence in favor of a hoax-
. Too many players.
. Inflated quantities of treasure.
. Many discrepancies exist in all documents.
. The Declaration of Independence is too hokey a key.
. Part 3 (list of 30 names) considered too little text.
. W.F. Friedman couldn't crack it.
. Why even encrypt parts 1 & 3?
. Why use multi-part text, and why different keys for each part?
. Difficult to keep treasure in ground if 30 men know where it was buried.
. Who'd leave it with other than your own family?
. The Inn Keeper waited an extra 10 years before opening box with
ciphers in it? Who would do this, curiousity runs too deep in
humans?
. Why did anybody waste time deciphering paper 2, which had no title?
1 & 3 had titles! These should have been deciphered first?
. Why not just one single letter?
. Statistical analysis show 1&3 similar in very obscure ways, that
2 differs. Did somebody else encipher it? And why?
Check length of keytexts, and forward/backward next word
displacement selections.
. Who could cross the entire country with that much gold and only
10 men and survive back then?
. Practically everybody who visited New Mexico before 1821, left
by way of the Pearly Gates, as the Spanish got almost every
tourist:-)
References:
"The Beale Treasure: A History of a Mystery", by Peter Viemeister,
Bedord, VA: Hamilton's, 1987. ISBN: 0-9608598-3-7. 230 pages.
"The Codebreakers", by David Kahn, pg 771, CCN 63-16109.
1967.
"Gold in the Blue Ridge, The True Story of the Beale Treasure",
by P.B. Innis & Walter Dean Innis, Devon Publ. Co., Wash, D.C.
1973.
"Signature Simulation and Certain Cryptographic Codes", Hammer,
Communications of the ACM, 14 (1), January 1971, pp. 3-14.
"How did TJB Encode B2?", Hammer, Cryptologia, 3 (1), Jan. 1979, pp. 9-15.
"Second Order Homophonic Ciphers", Hammer, Cryptologia, 12 (1) Jan. 1988,
pp 11-20.
==> cryptology/Feynman.p <==
What are the Feynman ciphers?
==> cryptology/Feynman.s <==
When I was a graduate student at Caltech, Professor Feynman showed me three
samples of code that he had been challenged with by a fellow scientist at
Los Alamos and which he had not been able to crack. I also was unable to
crack them. I posted them to Usenet and Jack C. Morrison of JPL cracked
the first one. It is a simple transposition cipher: split the text into
5-column pieces, then read from lower right upward. What results are the
opening lines of Chaucer's Canterbury Tales in Middle English.
1. Easier
MEOTAIHSIBRTEWDGLGKNLANEA
INOEEPEYSTNPEUOOEHRONLTIR
OSDHEOTNPHGAAETOHSZOTTENT
KEPADLYPHEODOWCFORRRNLCUE
EEEOPGMRLHNNDFTOENEALKEHH
EATTHNMESCNSHIRAETDAHLHEM
TETRFSWEDOEOENEGFHETAEDGH
RLNNGOAAEOCMTURRSLTDIDORE
HNHEHNAYVTIERHEENECTRNVIO
UOEHOTRNWSAYIFSNSHOEMRTRR
EUAUUHOHOOHCDCHTEEISEVRLS
KLIHIIAPCHRHSIHPSNWTOIISI
SHHNWEMTIEYAFELNRENLEERYI
PHBEROTEVPHNTYATIERTIHEEA
WTWVHTASETHHSDNGEIEAYNHHH
NNHTW
2. Harder
XUKEXWSLZJUAXUNKIGWFSOZRAWURO
RKXAOSLHROBXBTKCMUWDVPTFBLMKE
FVWMUXTVTWUIDDJVZKBRMCWOIWYDX
MLUFPVSHAGSVWUFWORCWUIDUJCNVT
TBERTUNOJUZHVTWKORSVRZSVVFSQX
OCMUWPYTRLGBMCYPOJCLRIYTVFCCM
UWUFPOXCNMCIWMSKPXEDLYIQKDJWI
WCJUMVRCJUMVRKXWURKPSEEIWZVXU
LEIOETOOFWKBIUXPXUGOWLFPWUSCH
3. New Message
WURVFXGJYTHEIZXSQXOBGSV
RUDOOJXATBKTARVIXPYTMYA
BMVUFXPXKUJVPLSDVTGNGOS
IGLWURPKFCVGELLRNNGLPYT
FVTPXAJOSCWRODORWNWSICL
FKEMOTGJYCRRAOJVNTODVMN
SQIVICRBICRUDCSKXYPDMDR
OJUZICRVFWXIFPXIVVIEPYT
DOIAVRBOOXWRAKPSZXTZKVR
OSWCRCFVEESOLWKTOBXAUXV
B
Chris Cole
Peregrine Systems
uunet!peregrine!chris
==> cryptology/Voynich.p <==
What are the Voynich ciphers?
Make REAL money with your website!
The entire AOH site is optimized to look best in Firefox® 2.0 on a widescreen monitor (1440x900 or better).
Site design & layout copyright © 1986-2008 AOH
We do not send spam. If you have received spam bearing an artofhacking.com email address, please forward it with full headers to abuse@artofhacking.com.