mathematics

Thanks to the folks at CCIL for hosting these pages.
remlaPS
Home Page Web Logs at CCIL

Dec_29_2006

I'm sure it doesn't matter to anyone, but I noticed tonight that if we
express the numbers in Pascal's Triangle in unary with 1 place in between
each numeral, then the rows are [2^n + n] "places" in size.

1 :- 1 = 2^0 + 0 (one 1, zero spaces)
1 1 :- 3 = 2^1 + 1 (two 1's, one space)
1 11 1 :- 6 = 2^2 + 2 (four 1's, two spaces)
1 111 111 1 :- 11 = 2^3 + 3 (eight 1's, three spaces)
1 1111 111111 1111 1 :- 20 = 2^4 + 4 (sixteen 1's, four spaces)
1 11111 1111111111 1111111111 11111 1 :- 37 = 2^5 + 5 (thirty-two 1's, 5 spaces)
...
...

How's that for stating the obvious?

AT&T has that sequence (2^n + n) here:
http://www.research.att.com/~njas/sequences/A006127

They don't say anything about Pascal's Triangle. They do mention
"Binomial transform of [1,2,1,1,1,1,1,...]." Looks similar, maybe, but I
don't know what that means.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#RowSizes122906
Dec_27_2006

Something else to look into if I ever get time...

1.) A graph can be seen as a triangular matrix.
2.) A matrix can be seeen as a list of polynomials, in terms of X.

What happens if we take a graph and do the following...
1.) Represent it as a matrix.
2.) Repeat while any polynomial in the matrix has more than 1 term
__2.0) Consider each polynomial to be in terms of some X.
__2.1) Convert all polynomials in terms of X to equivalent polynomials in terms of (X+1).
3.) Convert single term list of polynomials back to a graph.

I wonder if/how the start graph might be related to the ending graph.
Although... I'm having trouble visualizing that last step. I'm not quite
sure what it means without trying it. Maybe it can't even be done.

No time now. Just something I want to remember to try.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Curiosity122706
Dec_19_2006

http://en.wikipedia.org/wiki/Gaussian_elimination
An invertible matrix can be inverted using Gaussian
elimination. I think this might be what it means...

Start with this...
1 2 1
0 1 1
0 0 1

Append the identity matrix...
1 2 1 1 0 0
0 1 1 0 1 0
0 0 1 0 0 1

Subtract row 2 from row 1....
1 1 0 1 -1 0
0 1 1 0 1 0
0 0 1 0 0 1

Subtract row 2 from row 1 again...
1 0 -1 1 -2 0
0 1 1 0 1 0
0 0 1 0 0 1

Add row 3 to row 1...
1 0 0 1 -2 1
0 1 1 0 1 0
0 0 1 0 0 1

Subtract row 3 from row 2...
1 0 0 1 -2 1
0 1 0 0 1 -1
0 0 1 0 0 1

Remove the "leading" identity matrix, leaving the inverse.
1 -2 1
0 1 -1
0 0 1

I can almost remember doing something like this before. Almost.
That was a long time ago.


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#InvertMatrix121906
Dec_14_2006

10000_B -> G0000_(B/2) if (B/2) >= 17.
- B2B("10000",34,17,true);
val it = "G0000" : string
- B2B("10000",32,16,true);
val it = "100000" : string
- B2B("10000",36,18,true);
val it = "G0000" : string

100_B -> G00_(B/4) if (B/4) >= 17.
- B2B("100",240,60,true);
val it = "G00" : string
- B2B("100",200,50,true);
val it = "G00" : string
- B2B("100",160,40,true);
val it = "G00" : string
- B2B("100",100,25,true);
val it = "G00" : string
- B2B("100",80,20,true);
val it = "G00" : string
- B2B("100",68,17,true);
val it = "G00" : string
- B2B("100",64,16,true);
val it = "1000" : string

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreStableConversions121406pm
Dec_14_2006

Looks like 100_B always goes to 400_(B/2) when B is above 8 and even. It
also looks like 1000_B goes to 8000_(B/2) when B is above 16.

- B2B("100",4,2,true);
val it = "10000" : string
- B2B("100",6,3,true);
val it = "1100" : string
- B2B("100",8,4,true);
val it = "1000" : string
- B2B("100",10,5,true);
val it = "400" : string
- B2B("100",12,6,true);
val it = "400" : string
- B2B("100",14,7,true);
val it = "400" : string
- B2B("100",16,8,true);
val it = "400" : string
- B2B("100",18,9,true);
val it = "400" : string
- B2B("100",20,10,true);
val it = "400" : string
- B2B("100",22,11,true);
val it = "400" : string
- B2B("100",24,12,true);
val it = "400" : string
- B2B("100",26,13,true);
val it = "400" : string
- B2B("100",28,14,true);
val it = "400" : string
- B2B("100",30,15,true);
val it = "400" : string
- B2B("100",140,70,true);
val it = "400" : string

- B2B("1000",10,5,true);
val it = "13000" : string
- B2B("1000",12,6,true);
val it = "12000" : string
- B2B("1000",14,7,true);
val it = "11000" : string
- B2B("1000",16,8,true);
val it = "10000" : string
- B2B("1000",18,9,true);
val it = "8000" : string
- B2B("1000",20,10,true);
val it = "8000" : string
- B2B("1000",22,11,true);
val it = "8000" : string
- B2B("1000",24,12,true);
val it = "8000" : string

The algebra works out...
4(X/2)^2) = 4( X/2 ) (X/2) = 4X^2 / 4 = X^2.
8(X/2)^3 = 8(X/2)(X/2)(X/2)=8(X^3)/8=X^3.

So as soon as B/2 has a 4 digit in the case of 100 or an 8 digit in the
case of 1000, it makes sense that this would be the case...

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreSteadyConversions121406
Dec_02_2006

Someone posted on a prime mailing list I subscribe to that the primes make
up 29% of positive integers. They said they posted an attachment with a
proof, but if so, it didn't make it through the mailing list filter.

Someone else responded with a link to here:
http://primes.utm.edu/howmany.shtml

And said primes make up x/(log x), which goes to 0 as x goes to infinity.

There was some more discussion on the topic, revealing a surprising lack
of clarity from people I would have expected to know this answer off-hand.

So I've been thinking about it...

It seems we can write the primes & composites like this.

prime
composite
prime
composite
prime
composite
...
...

Since primes and composites are both infinite, we never run out of
numbers, so by inductive proof, primes are 50% of all positive integers.

But, we can write primes/composites like this.

prime
composite
composite
prime
composite
composite
prime
composite
composite
...
...

Still infinite, so inductive proof now tells us primes are 33% of all
positive integers (close to 29 ;-). But wait. How 'bout

prime
prime
composite
prime
prime
composite
prime
prime
composite
...
...

Still infinite. Now 67% of integers are primes.

So I think there's a simple inductive proof that X% of numbers are primes,
for any X I'd care to prove it for.

If I want to prove it for 29%, I just write
29 primes
71 composites
29 primes
71 composites
29 primes
71 composites
...
...

I remember once one of my professors said that there are mathematicians
who won't accept inductive proofs. I was puzzled about why. They
seemed rock-solid to me. Maybe this explains it?

At any rate, this phenomenon is puzzling to me. The 29% person was
apparently right, despite the existance of an infinite number of
counter-examples. Strange.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Puzzling120206
Nov_28_2006

Here's what that {n k} notation means... n is the distance, in rows, from
the root of the triangle. k is the distance from the beginning (or end)
of the row. Both start at 0.

{n k} (turned sideways) is the value of that cell in Pascal's triangle.
It can be calculated as... n!/k!(n-k)!

Here's some lisp code to demonstrate.

(defun factorial (X)
(cond ((< X 1) 0)
((equal X 1) 1)
(t (* X (factorial (- X 1))))))

(defun choose (n k)
(/ (factorial n) (* (factorial k) (factorial (- n k)))))

(defun RowChoose (Row K)
(cond ((= 0 K) (list 1))
((= K Row) (cons 1 (RowChoose Row (- K 1))))
(t (append (list (choose Row K)) (RowChoose Row (- K 1))))))

(RowChoose 0 0)
(1)
(RowChoose 1 1)
(1 1)
(RowChoose 2 2)
(1 2 1)
(RowChoose 3 3)
(1 3 3 1)
(RowChoose 4 4)
(1 4 6 4 1)
(RowChoose 5 5)
(1 5 10 10 5 1)
(RowChoose 6 6)
(1 6 15 20 15 6 1)
(RowChoose 7 7)
(1 7 21 35 35 21 7 1)
(RowChoose 8 8)
(1 8 28 56 70 56 28 8 1)

Hmmm. Now why did I want to know what it meant again? : -)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Choose112806
Nov_27_2006

http://www.math.uconn.edu/~troby/Hidden/4MattH/PTW/IdentitiesNamed.htm

I have trouble with the notation here, but I think Cat: #'s 3900000 and/or
3900022 ("Binomial Theorem" and "Binomial Theorem for falling factorial")
are probably related to the identities I just listed. However, the ones I
listed are of the form: (X+Y)^n == polynomial in X. The binomial theorems
give (X+Y)^n == polynomial in X & Y. One of these days I'm gonna have to
figure out what that

n
k

notation means.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#IdentityList112706
Nov_27_2006

I was thinking instead of sleeping and now I'm typing when I should be
studying... The following identities have become appparent.

(X+1)^2 = X^2 + 2X + 1
(X-1)^2 = X^2 - 2X + 1

(X+1)^3 = X^3 + 3X^2 + 3X + 1
(X-1)^3 = X^3 - 3X^2 + 3X - 1

(X+1)^4 = X^4 + 4X^3 + 6X^2 + 4X + 1
(X-1)^4 = X^4 - 4X^3 + 6X^2 - 4X + 1

(X+1)^5 = X^5 + 5X^4 + 10X^3 + 10X^2 + 5X + 1
(X-1)^5 = X^5 - 5X^4 + 10X^3 - 10X^2 + 5X - 1

(X+1)^6 = X^6 + 6X^5 + 15X^4 + 20X^3 + 15X^2 + 6X + 1
(X+1)^6 = X^6 - 6X^5 + 15X^4 - 20X^3 + 15X^2 - 6X + 1

...

Of course, we can do the same thing as before, take pascal's triangle to a
power, to get identities for {X +/- [anything]} (for positive variable
terms, anyway... I'm not thinking about negative ones yet.)

...
i.e.
(X+6)^3 = X^3 + 18X^2 + 108X + 216
(4+6)^3 = 1000 = (4^3) + 18(4^2) + 108(4) + 216 = 64 + 288 + 432 + 216 = 1000

I'm thinking these can't possibly be new identities though.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Identities112706
Nov_19_2006

I guess it shouldn't be a surprise that the up and down steady conversions
appear to contain the same sets of numbers.

Here's a base 3/4 example...

Down Conversion...
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadyDownConvert111606
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/SteadyConversionsDownSequence.txt
Running pascalbdown for base 4 -
Base 4 representations: 1, 2, 10, 11, 20, 100, 101,
Base 3 representations: 1, 2, 11, 12, 22, 121, 122,
Base 10 representations: 1, 2, 4, 5, 8, 16, 17,

Up Conversion:
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadySeries111606
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/SteadyConversionSeries.txt
Running pascalb for base 3 -
Base 3 representations: 1, 2, 11, 12, 22, 121, 122,
Base 4 representations: 1, 2, 10, 11, 20, 100, 101,
Base 10 representations: 1, 2, 4, 5, 8, 16, 17,

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadyConversions111906
Nov_16_2006

Here are the matching sequences going down 1 base instead of up...

http://taz.cs.wcupa.edu/~spalmer/PTIConvert/SteadyConversionsDownSequence.txt

i.e. 1011_B goes to 1343_(B-1) whenever B>4.

Here it is demonstrated for B's 17, 172, 199 and 240 to try a few more on
a whim...
- B2B("1011",17,16,true);
val it = "1343" : string
- B2B("1011",172,171,true);
val it = "1343" : string
- B2B("1011",199,198,true);
val it = "1343" : string
- B2B("1011",240,239,true);
val it = "1343" : string

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadyDownConvert111606
Nov_16_2006

In an easier to view format... Sequences of numerals which convert to
the same value when converted from base B to base B+1 where B is greater
than or equal to the base listed...

http://taz.cs.wcupa.edu/~spalmer/PTIConvert/SteadyConversionSeries.txt



This script shows the numerals which have steady conversions when converted from
base B to base (B+1), for all bases from the current base onwards.

For example, 1_B goes to 1_(B+1) regardless of B's value
Similarly, 121_B goes to 100_(B+1) from base 3 and up
and 1333_B goes to 1002_(B+1) whenever B is 4 or larger.

I guess that explanation is sufficient.


Running pascalb for base 2 -
Base 2 representations: 1, 11,
Base 3 representations: 1, 10,
Base 10 representations: 1, 3,
Return code: 0

Running pascalb for base 3 -
Base 3 representations: 1, 2, 11, 12, 22, 121, 122,
Base 4 representations: 1, 2, 10, 11, 20, 100, 101,
Base 10 representations: 1, 2, 4, 5, 8, 16, 17,
Return code: 0

Running pascalb for base 4 -
Base 4 representations: 1, 2, 3, 11, 12, 13, 22, 23, 33, 121, 122, 123, 132, 133, 1331, 1332, 1333,
Base 5 representations: 1, 2, 3, 10, 11, 12, 20, 21, 30, 100, 101, 102, 110, 111, 1000, 1001, 1002,
Base 10 representations: 1, 2, 3, 5, 6, 7, 10, 11, 15, 25, 26, 27, 30, 31, 125, 126, 127,
Return code: 0

Running pascalb for base 5 -
Base 5 representations: 1, 2, 3, 4, 11, 12, 13, 14, 22, 23, 24, 33, 34, 44, 121, 122, 123, 124, 132, 133, 134, 143, 144, 242, 243, 244, 1331, 1332, 1333, 1334, 1342, 1343, 1344,
Base 6 representations: 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40, 100, 101, 102, 103, 110, 111, 112, 120, 121, 200, 201, 202, 1000, 1001, 1002, 1003, 1010, 1011, 1012,
Base 10 representations: 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 18, 19, 24, 36, 37, 38, 39, 42, 43, 44, 48, 49, 72, 73, 74, 216, 217, 218, 219, 222, 223, 224,
Return code: 0

Running pascalb for base 6 -
Base 6 representations: 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 45, 55, 121, 122, 123, 124, 125, 132, 133, 134, 135, 143, 144, 145, 154, 155, 242, 243, 244, 245, 253, 254, 255, 1331, 1332, 1333, 1334, 1335, 1342, 1343, 1344, 1345, 1353, 1354, 1355, 1452, 1453, 1454, 1455,
Base 7 representations: 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 20, 21, 22, 23, 30, 31, 32, 40, 41, 50, 100, 101, 102, 103, 104, 110, 111, 112, 113, 120, 121, 122, 130, 131, 200, 201, 202, 203, 210, 211, 212, 1000, 1001, 1002, 1003, 1004, 1010, 1011, 1012, 1013, 1020, 1021, 1022, 1100, 1101, 1102, 1103,
Base 10 representations: 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 16, 17, 21, 22, 23, 28, 29, 35, 49, 50, 51, 52, 53, 56, 57, 58, 59, 63, 64, 65, 70, 71, 98, 99, 100, 101, 105, 106, 107, 343, 344, 345, 346, 347, 350, 351, 352, 353, 357, 358, 359, 392, 393, 394, 395,
Return code: 0

Running pascalb for base 7 -
Base 7 representations: 1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 16, 22, 23, 24, 25, 26, 33, 34, 35, 36, 44, 45, 46, 55, 56, 66, 121, 122, 123, 124, 125, 126, 132, 133, 134, 135, 136, 143, 144, 145, 146, 154, 155, 156, 165, 166, 242, 243, 244, 245, 246, 253, 254, 255, 256, 264, 265, 266, 363, 364, 365, 366, 1331, 1332, 1333, 1334, 1335, 1336, 1342, 1343, 1344, 1345, 1346, 1353, 1354, 1355, 1356, 1364, 1365, 1366, 1452, 1453, 1454, 1455, 1456, 1463, 1464, 1465, 1466, 2662, 2663, 2664, 2665, 2666, 14641, 14642, 14643, 14644, 14645, 14646, 14652, 14653, 14654, 14655, 14656, 14663, 14664, 14665, 14666,
Base 8 representations: 1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 30, 31, 32, 33, 40, 41, 42, 50, 51, 60, 100, 101, 102, 103, 104, 105, 110, 111, 112, 113, 114, 120, 121, 122, 123, 130, 131, 132, 140, 141, 200, 201, 202, 203, 204, 210, 211, 212, 213, 220, 221, 222, 300, 301, 302, 303, 1000, 1001, 1002, 1003, 1004, 1005, 1010, 1011, 1012, 1013, 1014, 1020, 1021, 1022, 1023, 1030, 1031, 1032, 1100, 1101, 1102, 1103, 1104, 1110, 1111, 1112, 1113, 2000, 2001, 2002, 2003, 2004, 10000, 10001, 10002, 10003, 10004, 10005, 10010, 10011, 10012, 10013, 10014, 10020, 10021, 10022, 10023,
Base 10 representations: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 16, 17, 18, 19, 20, 24, 25, 26, 27, 32, 33, 34, 40, 41, 48, 64, 65, 66, 67, 68, 69, 72, 73, 74, 75, 76, 80, 81, 82, 83, 88, 89, 90, 96, 97, 128, 129, 130, 131, 132, 136, 137, 138, 139, 144, 145, 146, 192, 193, 194, 195, 512, 513, 514, 515, 516, 517, 520, 521, 522, 523, 524, 528, 529, 530, 531, 536, 537, 538, 576, 577, 578, 579, 580, 584, 585, 586, 587, 1024, 1025, 1026, 1027, 1028, 4096, 4097, 4098, 4099, 4100, 4101, 4104, 4105, 4106, 4107, 4108, 4112, 4113, 4114, 4115,
Return code: 0

Running pascalb for base 8 -
Base 8 representations: 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15, 16, 17, 22, 23, 24, 25, 26, 27, 33, 34, 35, 36, 37, 44, 45, 46, 47, 55, 56, 57, 66, 67, 77, 121, 122, 123, 124, 125, 126, 127, 132, 133, 134, 135, 136, 137, 143, 144, 145, 146, 147, 154, 155, 156, 157, 165, 166, 167, 176, 177, 242, 243, 244, 245, 246, 247, 253, 254, 255, 256, 257, 264, 265, 266, 267, 275, 276, 277, 363, 364, 365, 366, 367, 374, 375, 376, 377, 1331, 1332, 1333, 1334, 1335, 1336, 1337, 1342, 1343, 1344, 1345, 1346, 1347, 1353, 1354, 1355, 1356, 1357, 1364, 1365, 1366, 1367, 1375, 1376, 1377, 1452, 1453, 1454, 1455, 1456, 1457, 1463, 1464, 1465, 1466, 1467, 1474, 1475, 1476, 1477, 1573, 1574, 1575, 1576, 1577, 2662, 2663, 2664, 2665, 2666, 2667, 2673, 2674, 2675, 2676, 2677, 14641, 14642, 14643, 14644, 14645, 14646, 14647, 14652, 14653, 14654, 14655, 14656, 14657, 14663, 14664, 14665, 14666, 14667, 14674, 14675, 14676, 14677, 14762, 14763, 14764, 14765, 14766, 14767, 14773, 14774, 14775, 14776, 14777,
Base 9 representations: 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 30, 31, 32, 33, 34, 40, 41, 42, 43, 50, 51, 52, 60, 61, 70, 100, 101, 102, 103, 104, 105, 106, 110, 111, 112, 113, 114, 115, 120, 121, 122, 123, 124, 130, 131, 132, 133, 140, 141, 142, 150, 151, 200, 201, 202, 203, 204, 205, 210, 211, 212, 213, 214, 220, 221, 222, 223, 230, 231, 232, 300, 301, 302, 303, 304, 310, 311, 312, 313, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1010, 1011, 1012, 1013, 1014, 1015, 1020, 1021, 1022, 1023, 1024, 1030, 1031, 1032, 1033, 1040, 1041, 1042, 1100, 1101, 1102, 1103, 1104, 1105, 1110, 1111, 1112, 1113, 1114, 1120, 1121, 1122, 1123, 1200, 1201, 1202, 1203, 1204, 2000, 2001, 2002, 2003, 2004, 2005, 2010, 2011, 2012, 2013, 2014, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10010, 10011, 10012, 10013, 10014, 10015, 10020, 10021, 10022, 10023, 10024, 10030, 10031, 10032, 10033, 10100, 10101, 10102, 10103, 10104, 10105, 10110, 10111, 10112, 10113, 10114,
Base 10 representations: 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 18, 19, 20, 21, 22, 23, 27, 28, 29, 30, 31, 36, 37, 38, 39, 45, 46, 47, 54, 55, 63, 81, 82, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 101, 102, 103, 108, 109, 110, 111, 117, 118, 119, 126, 127, 162, 163, 164, 165, 166, 167, 171, 172, 173, 174, 175, 180, 181, 182, 183, 189, 190, 191, 243, 244, 245, 246, 247, 252, 253, 254, 255, 729, 730, 731, 732, 733, 734, 735, 738, 739, 740, 741, 742, 743, 747, 748, 749, 750, 751, 756, 757, 758, 759, 765, 766, 767, 810, 811, 812, 813, 814, 815, 819, 820, 821, 822, 823, 828, 829, 830, 831, 891, 892, 893, 894, 895, 1458, 1459, 1460, 1461, 1462, 1463, 1467, 1468, 1469, 1470, 1471, 6561, 6562, 6563, 6564, 6565, 6566, 6567, 6570, 6571, 6572, 6573, 6574, 6575, 6579, 6580, 6581, 6582, 6583, 6588, 6589, 6590, 6591, 6642, 6643, 6644, 6645, 6646, 6647, 6651, 6652, 6653, 6654, 6655,
Return code: 0

Running pascalb for base 9 -
Base 9 representations: 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 27, 28, 33, 34, 35, 36, 37, 38, 44, 45, 46, 47, 48, 55, 56, 57, 58, 66, 67, 68, 77, 78, 88, 121, 122, 123, 124, 125, 126, 127, 128, 132, 133, 134, 135, 136, 137, 138, 143, 144, 145, 146, 147, 148, 154, 155, 156, 157, 158, 165, 166, 167, 168, 176, 177, 178, 187, 188, 242, 243, 244, 245, 246, 247, 248, 253, 254, 255, 256, 257, 258, 264, 265, 266, 267, 268, 275, 276, 277, 278, 286, 287, 288, 363, 364, 365, 366, 367, 368, 374, 375, 376, 377, 378, 385, 386, 387, 388, 484, 485, 486, 487, 488, 1331, 1332, 1333, 1334, 1335, 1336, 1337, 1338, 1342, 1343, 1344, 1345, 1346, 1347, 1348, 1353, 1354, 1355, 1356, 1357, 1358, 1364, 1365, 1366, 1367, 1368, 1375, 1376, 1377, 1378, 1386, 1387, 1388, 1452, 1453, 1454, 1455, 1456, 1457, 1458, 1463, 1464, 1465, 1466, 1467, 1468, 1474, 1475, 1476, 1477, 1478, 1485, 1486, 1487, 1488, 1573, 1574, 1575, 1576, 1577, 1578, 1584, 1585, 1586, 1587, 1588, 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2673, 2674, 2675, 2676, 2677, 2678, 2684, 2685, 2686, 2687, 2688, 2783, 2784, 2785, 2786, 2787, 2788, 14641, 14642, 14643, 14644, 14645, 14646, 14647, 14648, 14652, 14653, 14654, 14655, 14656, 14657, 14658, 14663, 14664, 14665, 14666, 14667, 14668, 14674, 14675, 14676, 14677, 14678, 14685, 14686, 14687, 14688, 14762, 14763, 14764, 14765, 14766, 14767, 14768, 14773, 14774, 14775, 14776, 14777, 14778, 14784, 14785, 14786, 14787, 14788, 14883, 14884, 14885, 14886, 14887, 14888,
Base 10 representations: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 30, 31, 32, 33, 34, 35, 40, 41, 42, 43, 44, 50, 51, 52, 53, 60, 61, 62, 70, 71, 80, 100, 101, 102, 103, 104, 105, 106, 107, 110, 111, 112, 113, 114, 115, 116, 120, 121, 122, 123, 124, 125, 130, 131, 132, 133, 134, 140, 141, 142, 143, 150, 151, 152, 160, 161, 200, 201, 202, 203, 204, 205, 206, 210, 211, 212, 213, 214, 215, 220, 221, 222, 223, 224, 230, 231, 232, 233, 240, 241, 242, 300, 301, 302, 303, 304, 305, 310, 311, 312, 313, 314, 320, 321, 322, 323, 400, 401, 402, 403, 404, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1010, 1011, 1012, 1013, 1014, 1015, 1016, 1020, 1021, 1022, 1023, 1024, 1025, 1030, 1031, 1032, 1033, 1034, 1040, 1041, 1042, 1043, 1050, 1051, 1052, 1100, 1101, 1102, 1103, 1104, 1105, 1106, 1110, 1111, 1112, 1113, 1114, 1115, 1120, 1121, 1122, 1123, 1124, 1130, 1131, 1132, 1133, 1200, 1201, 1202, 1203, 1204, 1205, 1210, 1211, 1212, 1213, 1214, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2010, 2011, 2012, 2013, 2014, 2015, 2020, 2021, 2022, 2023, 2024, 2100, 2101, 2102, 2103, 2104, 2105, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10010, 10011, 10012, 10013, 10014, 10015, 10016, 10020, 10021, 10022, 10023, 10024, 10025, 10030, 10031, 10032, 10033, 10034, 10040, 10041, 10042, 10043, 10100, 10101, 10102, 10103, 10104, 10105, 10106, 10110, 10111, 10112, 10113, 10114, 10115, 10120, 10121, 10122, 10123, 10124, 10200, 10201, 10202, 10203, 10204, 10205,
Base 10 representations: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 30, 31, 32, 33, 34, 35, 40, 41, 42, 43, 44, 50, 51, 52, 53, 60, 61, 62, 70, 71, 80, 100, 101, 102, 103, 104, 105, 106, 107, 110, 111, 112, 113, 114, 115, 116, 120, 121, 122, 123, 124, 125, 130, 131, 132, 133, 134, 140, 141, 142, 143, 150, 151, 152, 160, 161, 200, 201, 202, 203, 204, 205, 206, 210, 211, 212, 213, 214, 215, 220, 221, 222, 223, 224, 230, 231, 232, 233, 240, 241, 242, 300, 301, 302, 303, 304, 305, 310, 311, 312, 313, 314, 320, 321, 322, 323, 400, 401, 402, 403, 404, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1010, 1011, 1012, 1013, 1014, 1015, 1016, 1020, 1021, 1022, 1023, 1024, 1025, 1030, 1031, 1032, 1033, 1034, 1040, 1041, 1042, 1043, 1050, 1051, 1052, 1100, 1101, 1102, 1103, 1104, 1105, 1106, 1110, 1111, 1112, 1113, 1114, 1115, 1120, 1121, 1122, 1123, 1124, 1130, 1131, 1132, 1133, 1200, 1201, 1202, 1203, 1204, 1205, 1210, 1211, 1212, 1213, 1214, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2010, 2011, 2012, 2013, 2014, 2015, 2020, 2021, 2022, 2023, 2024, 2100, 2101, 2102, 2103, 2104, 2105, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10010, 10011, 10012, 10013, 10014, 10015, 10016, 10020, 10021, 10022, 10023, 10024, 10025, 10030, 10031, 10032, 10033, 10034, 10040, 10041, 10042, 10043, 10100, 10101, 10102, 10103, 10104, 10105, 10106, 10110, 10111, 10112, 10113, 10114, 10115, 10120, 10121, 10122, 10123, 10124, 10200, 10201, 10202, 10203, 10204, 10205,
Return code: 0

Running pascalb for base 10 -
Base 10 representations: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 121, 122, 123, 124, 125, 126, 127, 128, 129, 132, 133, 134, 135, 136, 137, 138, 139, 143, 144, 145, 146, 147, 148, 149, 154, 155, 156, 157, 158, 159, 165, 166, 167, 168, 169, 176, 177, 178, 179, 187, 188, 189, 198, 199, 242, 243, 244, 245, 246, 247, 248, 249, 253, 254, 255, 256, 257, 258, 259, 264, 265, 266, 267, 268, 269, 275, 276, 277, 278, 279, 286, 287, 288, 289, 297, 298, 299, 363, 364, 365, 366, 367, 368, 369, 374, 375, 376, 377, 378, 379, 385, 386, 387, 388, 389, 396, 397, 398, 399, 484, 485, 486, 487, 488, 489, 495, 496, 497, 498, 499, 1331, 1332, 1333, 1334, 1335, 1336, 1337, 1338, 1339, 1342, 1343, 1344, 1345, 1346, 1347, 1348, 1349, 1353, 1354, 1355, 1356, 1357, 1358, 1359, 1364, 1365, 1366, 1367, 1368, 1369, 1375, 1376, 1377, 1378, 1379, 1386, 1387, 1388, 1389, 1397, 1398, 1399, 1452, 1453, 1454, 1455, 1456, 1457, 1458, 1459, 1463, 1464, 1465, 1466, 1467, 1468, 1469, 1474, 1475, 1476, 1477, 1478, 1479, 1485, 1486, 1487, 1488, 1489, 1496, 1497, 1498, 1499, 1573, 1574, 1575, 1576, 1577, 1578, 1579, 1584, 1585, 1586, 1587, 1588, 1589, 1595, 1596, 1597, 1598, 1599, 1694, 1695, 1696, 1697, 1698, 1699, 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2669, 2673, 2674, 2675, 2676, 2677, 2678, 2679, 2684, 2685, 2686, 2687, 2688, 2689, 2695, 2696, 2697, 2698, 2699, 2783, 2784, 2785, 2786, 2787, 2788, 2789, 2794, 2795, 2796, 2797, 2798, 2799, 3993, 3994, 3995, 3996, 3997, 3998, 3999, 14641, 14642, 14643, 14644, 14645, 14646, 14647, 14648, 14649, 14652, 14653, 14654, 14655, 14656, 14657, 14658, 14659, 14663, 14664, 14665, 14666, 14667, 14668, 14669, 14674, 14675, 14676, 14677, 14678, 14679, 14685, 14686, 14687, 14688, 14689, 14696, 14697, 14698, 14699, 14762, 14763, 14764, 14765, 14766, 14767, 14768, 14769, 14773, 14774, 14775, 14776, 14777, 14778, 14779, 14784, 14785, 14786, 14787, 14788, 14789, 14795, 14796, 14797, 14798, 14799, 14883, 14884, 14885, 14886, 14887, 14888, 14889, 14894, 14895, 14896, 14897, 14898, 14899, 15972, 15973, 15974, 15975, 15976, 15977, 15978, 15979, 15983, 15984, 15985, 15986, 15987, 15988, 15989, 15994, 15995, 15996, 15997, 15998, 15999,
Base 11 representations: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34, 35, 36, 40, 41, 42, 43, 44, 45, 50, 51, 52, 53, 54, 60, 61, 62, 63, 70, 71, 72, 80, 81, 90, 100, 101, 102, 103, 104, 105, 106, 107, 108, 110, 111, 112, 113, 114, 115, 116, 117, 120, 121, 122, 123, 124, 125, 126, 130, 131, 132, 133, 134, 135, 140, 141, 142, 143, 144, 150, 151, 152, 153, 160, 161, 162, 170, 171, 200, 201, 202, 203, 204, 205, 206, 207, 210, 211, 212, 213, 214, 215, 216, 220, 221, 222, 223, 224, 225, 230, 231, 232, 233, 234, 240, 241, 242, 243, 250, 251, 252, 300, 301, 302, 303, 304, 305, 306, 310, 311, 312, 313, 314, 315, 320, 321, 322, 323, 324, 330, 331, 332, 333, 400, 401, 402, 403, 404, 405, 410, 411, 412, 413, 414, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1010, 1011, 1012, 1013, 1014, 1015, 1016, 1017, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1030, 1031, 1032, 1033, 1034, 1035, 1040, 1041, 1042, 1043, 1044, 1050, 1051, 1052, 1053, 1060, 1061, 1062, 1100, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1120, 1121, 1122, 1123, 1124, 1125, 1130, 1131, 1132, 1133, 1134, 1140, 1141, 1142, 1143, 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1210, 1211, 1212, 1213, 1214, 1215, 1220, 1221, 1222, 1223, 1224, 1300, 1301, 1302, 1303, 1304, 1305, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2020, 2021, 2022, 2023, 2024, 2025, 2030, 2031, 2032, 2033, 2034, 2100, 2101, 2102, 2103, 2104, 2105, 2106, 2110, 2111, 2112, 2113, 2114, 2115, 3000, 3001, 3002, 3003, 3004, 3005, 3006, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10010, 10011, 10012, 10013, 10014, 10015, 10016, 10017, 10020, 10021, 10022, 10023, 10024, 10025, 10026, 10030, 10031, 10032, 10033, 10034, 10035, 10040, 10041, 10042, 10043, 10044, 10050, 10051, 10052, 10053, 10100, 10101, 10102, 10103, 10104, 10105, 10106, 10107, 10110, 10111, 10112, 10113, 10114, 10115, 10116, 10120, 10121, 10122, 10123, 10124, 10125, 10130, 10131, 10132, 10133, 10134, 10200, 10201, 10202, 10203, 10204, 10205, 10206, 10210, 10211, 10212, 10213, 10214, 10215, 11000, 11001, 11002, 11003, 11004, 11005, 11006, 11007, 11010, 11011, 11012, 11013, 11014, 11015, 11016, 11020, 11021, 11022, 11023, 11024, 11025,
Base 10 representations: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 121, 122, 123, 124, 125, 126, 127, 128, 129, 132, 133, 134, 135, 136, 137, 138, 139, 143, 144, 145, 146, 147, 148, 149, 154, 155, 156, 157, 158, 159, 165, 166, 167, 168, 169, 176, 177, 178, 179, 187, 188, 189, 198, 199, 242, 243, 244, 245, 246, 247, 248, 249, 253, 254, 255, 256, 257, 258, 259, 264, 265, 266, 267, 268, 269, 275, 276, 277, 278, 279, 286, 287, 288, 289, 297, 298, 299, 363, 364, 365, 366, 367, 368, 369, 374, 375, 376, 377, 378, 379, 385, 386, 387, 388, 389, 396, 397, 398, 399, 484, 485, 486, 487, 488, 489, 495, 496, 497, 498, 499, 1331, 1332, 1333, 1334, 1335, 1336, 1337, 1338, 1339, 1342, 1343, 1344, 1345, 1346, 1347, 1348, 1349, 1353, 1354, 1355, 1356, 1357, 1358, 1359, 1364, 1365, 1366, 1367, 1368, 1369, 1375, 1376, 1377, 1378, 1379, 1386, 1387, 1388, 1389, 1397, 1398, 1399, 1452, 1453, 1454, 1455, 1456, 1457, 1458, 1459, 1463, 1464, 1465, 1466, 1467, 1468, 1469, 1474, 1475, 1476, 1477, 1478, 1479, 1485, 1486, 1487, 1488, 1489, 1496, 1497, 1498, 1499, 1573, 1574, 1575, 1576, 1577, 1578, 1579, 1584, 1585, 1586, 1587, 1588, 1589, 1595, 1596, 1597, 1598, 1599, 1694, 1695, 1696, 1697, 1698, 1699, 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2669, 2673, 2674, 2675, 2676, 2677, 2678, 2679, 2684, 2685, 2686, 2687, 2688, 2689, 2695, 2696, 2697, 2698, 2699, 2783, 2784, 2785, 2786, 2787, 2788, 2789, 2794, 2795, 2796, 2797, 2798, 2799, 3993, 3994, 3995, 3996, 3997, 3998, 3999, 14641, 14642, 14643, 14644, 14645, 14646, 14647, 14648, 14649, 14652, 14653, 14654, 14655, 14656, 14657, 14658, 14659, 14663, 14664, 14665, 14666, 14667, 14668, 14669, 14674, 14675, 14676, 14677, 14678, 14679, 14685, 14686, 14687, 14688, 14689, 14696, 14697, 14698, 14699, 14762, 14763, 14764, 14765, 14766, 14767, 14768, 14769, 14773, 14774, 14775, 14776, 14777, 14778, 14779, 14784, 14785, 14786, 14787, 14788, 14789, 14795, 14796, 14797, 14798, 14799, 14883, 14884, 14885, 14886, 14887, 14888, 14889, 14894, 14895, 14896, 14897, 14898, 14899, 15972, 15973, 15974, 15975, 15976, 15977, 15978, 15979, 15983, 15984, 15985, 15986, 15987, 15988, 15989, 15994, 15995, 15996, 15997, 15998, 15999,
Return code: 0
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadySeries111606
Oct_14_2006

Here's the framework for a general proof for converting a polynomial from
being in terms of X to being in terms of X+1. I think I'll have to find
some time with a pen and paper to actually complete it. It's gonna be
tedious, but doesn't look too complicated.

The keys are the fact that the first column is all 0's, except for the top
and the alternating signs. The k-digit matrix multiplication takes care
of digits up through k and the 1st row adds just the (k+1) digit.
Everything else drops out because of the (X+1) palindromes
coupled with the alternating signs.

Assume: Ak=[d0k d0k-1 ... d_0_1 d_0_0]
APk=dkX^k + d(k-1)X^(k-1) + ... + d1X + d0

Find: (new dk's)
Ak+1=[dk+1 dk dk-1 ... d1 d0]
Pk+1={
1, - Pk{2,1}+Pk{2,2}, + Pk{2,2}+Pk{2,3}, ...,
Pk(2,k-2)+Pk(2,k-1),Pk(2,k-1),Pk(2,k),1
{0
0 {Pk,k}
..
..
0}

Number Pk+1 slots, 1 through k, left to right and top to bottom.

A*[Pk+1] =
[(dk+1) (- (dk+1)(Pk+1(1,2)) + SUM(dj*Pj(2,j+1));j=1,k) ...
((dk+1) (Pk+1(1,3) + SUM(dj*Pj(3,j+1);j=1,k) + ...
(- (dk+1) (Pk+1(1,k) + SUM(dj*Pj(k-1);j=1,k) + ...
((dk+1) (Pk+1(1,k+1)) + SUM(dj*Pj(k);j=1,k)]

So the SUM terms drop out, by the inductive hypothesis, becoming
L=d(k)X^k + d(k)X^(k-1) + ... + d1X + d0

Leaving
= (d0)(X+1)^(k+1) - (d0)(Pk+1(1,2)(X+1))^k + (d0)(Pk+1(1,3))(X+1)^k-1 -
... - (d0X) + dk+1 + L

= d0(X+1)^k -
(Pk(1,1) + Pk(1,2))(X+1)^(k-1) +
(Pk(1,2) + Pk(1,3))(X+1)^(k-2) -
...
(Pk(1,k-3) + Pk(1,k-2))(X+1)^2 -
(Pk(1,k-2) + Pk(1,k-1))(X+1) +
(Pk(1,k-1) + Pk(1,k)) + L

Since the Pk(x,y) terms have alternating signs, and the (X+1)'s multiply
out to palindromes, everything drops out except d0(X+1)^(k+1). The d0
terms other than d0X^K will drop out between raising (X+1)^(k+1) and all
the remnants from the trailing terms.

Completing the proof, left behind will be
d0(X^(k+1)) + L


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#GeneralProofB+1-101406
Oct_13_2006

Here's the proof when converting a 5 term polynomial from being in terms
of X to terms of (X+1). (i.e. 5 digit numeral)

5 digits: d4X^4 + d3X^3 + d2X^2 + d1X + d0
==> A=[d4 d3 d2 d1 d0]
P={
1,-4,6,-4,1
0,1,-3,3,-1
0,0,1,-2,1
0,0,0,1,-1
0,0,0,0,1
}

AP=[(d4) (-4d4 + d3) (6d4 - 3d3 + d2) (-4d4 + 3d3 - 2d2 + d1) (d4-d3+d2-d1+d0)]

=>d4(X+1)^4 - (4d4 - d3)(X+1)^3 + (6d4 - 3d3 + d2)(X+1)^2 -
(4d4 - 3d3 + 2d2 - d1)(X+1) + (d4-d3+d2-d1+d0)
=d4(X^4 + 4X^3 + 6X^2 + 4X +1) - (4d4 - d3)(X^3 + 3X^2 + 3X + 1) +
(6d4 - 3d3 + d2)(X^2 + 2X + 1) - (4d4 + 3d3 - 2d2 + d1)(X+1) +
(d4-d3+d2-d1+d0)

=d4X^4 + 4d4X^3 + 6d4X^2 + 4d4X + d4 - 4d4X^3 - 12d4X^2 - 12d4X - 4d4 +
d3X^3 + 3d3X^2 + 3d3X + d3 + 6d4X^2 + 12d4X + 6d4 - 3d3X^2 - 6d3X -
3d3 + d2X^2 + 2d2dX + d2 - 4d4X - 4d4 + 3d3X + 3d3 - 2d2X - 2d2 + d1X +
d1 + d4 - d3 + d2 - d1 + d0

=d4X^4 + d3X^3 + d2X^2 + d1X + d0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FiveDigitProof101306
Oct_12_2006

I just tested a number of base B to base B-6 conversions using Pascal's
Triangle to the 6th power. As suspected, all were successful. Someone's
got lots of proving to do... (or maybe not)

Here's the matrix to reduce terms of the polynomial from X to X-6 (for 8
digits)

/* Pascal's triangle ** 6 for base B to base B-6 conversion */
{1, 42, 756, 7560, 45360, 163296, 326592, 279936,
0, 1, 36, 540, 4320, 19440, 46656, 46656,
0, 0, 1, 30, 360, 2160, 6480, 7776,
0, 0, 0, 1, 24, 216, 864, 1296,
0, 0, 0, 0, 1, 18, 108, 216,
0, 0, 0, 0, 0, 1, 12, 36,
0, 0, 0, 0, 0, 0, 1, 6,
0, 0, 0, 0, 0, 0, 0, 1};


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#DownBy6-101206
Oct_10_2006

http://www.freepatentsonline.com/6236340.html
>
> The modulation encoder of claim 8 wherein the base conversion circuit
> performs a matrix multiplication, where W is a matrix representing
> coefficients defined as:
>
> TBL W = 1 1 1 1 1 1 1 1; 0 1 2 3 4 5 6 7; 0 0 1 3 6 10 0 6; 0 0 0 1 4 10
> 6 6; 0 0 0 0 1 5 1 7; 0 0 0 0 0 1 7 8; 0 0 0 0 0 0 1 8; 0 0 0 0 0 0 0 1;
>
> dd={d(31:28) d(27:24) d(23:20) d(19:16) d(15:12) d(11:8) d(7:4) d(3:0)}
>
> and where the intermediate values b are provided by:
>
> b{7:0}=W*dd',
>
> and where * is matrix multiplication.

Their coefficients are different fom Pascal's.... they don't have Pascal's
triangle or it's inverse... but some are close. Looks like they're going
from base 16 to base 15 by matrix multiplication. I think we're also
different because their multiplication order is transformation-matrix then
polynomial, not polynomial times transformation-matrix.

I'm getting tired and my head's getting foggy. I'll have to read it more
carefully another time. I'm surprised to find what looks like yet another
matrix multiplication solution to base conversion, but the fact that it
was just filed in 1999 and approved in 2001 makes me think maybe this
Pascal's triangle thing really isn't known. If it were, why wouldn't they
have used that method instead of this one?

I don't know, though, that's still hard to swallow. People have been
looking at Pascal's triangle for centuries. How could something this
straight-forward have slipped through? It's not just computers and base
conversion. There must have been someone who wanted to convert
polynomials from being in terms of X to being in terms of X+1 or X-1 at
some time, even before the advent of computers.

I'll keep investigating it and keep looking around. I expect that one of
these days I'll find that I'm retreading old ground. No matter. I'm
having fun.

I thought I found it in that patent, but now I'm thinking... not quite.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MaybePatented101006
Oct_10_2006

Here's the proof that Pascal's inverse positioned as below maps a 4 digit
polynomial in terms of X to a 4 digit polynomial in terms of (X+1). The
math's getting tedious now. I'm gonna have to start thinking in terms of
induction or the algebra is gonna run away from me.

4 digits: d3X^3 + d2X^2 + d1X + d0
A=[d3 d2 d1 d0]
B=
1,-3,3,-1
0,1,-2,1
0,0,1,-1
0,0,0,1

AB=[(d3) ( -3d3 + d2 ) (3d3 -2d2 + d1) (-d3 + d2 -d1 + d0)]
=>(d3)(X+1)^3 + (-3d3 + d2)(X+1)^2 + (3d3 -2d2 + d1)(X+1) + (-d3 + d2 - d1 + d0)
=d3(X^3 + 3X^2 + 3X + 1) + (-3d3 + d2)(X^2 + 2X +1) + (3d3 - 2d2 + d1)(X + 1) - d3 + d2 - d1 + d0
=d3X^3 + 3d3X^2 + 3d3X + d3 + d2X^2 + 2d2X + d2 -3d3X^2 - 6d3X - 3d3 + 3d3X - 2d2X + d1X + 3d3 - 2d2 + d1 -d3 + d2 -d1 + d0
=d3X^3 + d2X^2 + d1X + d0

I still can't believe I can't find this on the web anywhere. I looked at
Wolfram's site and wikipedia again tonight. They talk about lots of uses
for Pascal's triangle, but not a word about converting the terms of
polynomials or converting bases. Not even much about reorienting Pascal's
triangle so it's rooted in different places in the matrix.

Oh. I also changed the pascalb program (original version here)...
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/pascalb.cpp.txt

...to perform matrix multiplications by Pascal's triangle (instead of it's
inverse) in the above orientation. I ran it on a half dozen bases and
they all did appear to convert correctly from base B to B-1, as guessed
this morning.

I'm not gonna bother saving the modified pascalb or that data. The
changes were trivial.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FourDigitProof101006
Oct_10_2006

Apparently, multiplying by Pascal's triangle with the same reorientation
as the B+1 matrix is a good candidate for a B to B-1 conversion.

So to summarize... If I start with a base B numeral, N and a matrix, M_i,

==
if M_i = M1=
...
...
1,-2, 1
0, 1,-1
0, 0, 1

then
N * (M1) = N in terms of B+1.

==
if M_i = M2=
...
...
1, 2, 1
0, 1, 1
0, 0, 1

then
N * (M2) = N in terms of B-1.

==
Further, I guess that
N * [M1 ** P] = a polynomial in terms of B+P which is equal to N in terms of B.

and
N * [M2 ** P] = a polynomial in terms of B-P which is equal to N in terms of B.

==
The only thing I've proven so far is N * [M1] for 1 through 3 digits.

The rest is still "conjecture" (from my perspective. Probably already
proven by someone else.)

==
All resultant polynomials can be converted to legal numerals using the
method described before...
(LegalD, here for example:
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FiveDigits100106
)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PTriangleSummary100906
Oct_09_2006

Here's the proof for the 1, 2 and 3 digit cases. The algebra's not bad
yet. Gonna take some more time 'til I can see the overall proof by
induction though.

For 1, 2 and 3 digits, multiplying by Pascal's triangle's inverse
(reoriented) does convert a polynomial in terms of X to a polynomial in
terms of X+1. As expected.

1 digit: d0
A=[d0]
B=[1]
AB = d0(1)
==> d0x^0 = d0x1^0

2 digits: d1X + d0
A=[d1 d0]
B=
1, -1
0, 1
AB =
[(d1 + 0d0) (d0 - d1)]
=> (d1)(X+1) + (d0 - d1)
= d1X + d1 + d0 - d1
= d1X + d0

3 digits: d2X^2 + d1X + d0
A=[d2 d1 d0]
B=
1,-2,1
0,1,-1
0,0,1
AB=[(d2) (-2d2 + d1) (d2 - d1 + d0)]
==> (d2(X+1)^2) + (-2d2 + d1)(X+1) + (d2 - d1 + d0)
=d2(X^2 + 2X + 1) + (-2d2X - 2d2 + d1X + d1) + (d2 - d1 + d0)
=d2(X^2 + 2X + 1) + (-2d2X - 2d2 + d1X + d1) + (d2 - d1 + d0)
=d2X^2 + 2d2X + d2 - 2d2X - 2d2 + d1X + d1 + d2 - d1 + d0
=d2X^2 + d1X + d0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#StartProving100806
Oct_08_2006

For N=2 through N=10, Numerals (up to 8 digits) which go to the same
numeral after conversion from base B to base B+1 for all bases, B,
where B >= N.
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/StableConversions.txt

For example, 1455 first appears in base 6, so 1455_b will go to 1103_(b+1)
any time b >= 6.

==
Also, running another timing comparison here...
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/BCompareResults3.txt

I added a check to divb which will hopefully prevent it from going into
a spin cycle. Killed the previous check and started another. I think I
set this one to go to base 15 instead of 20.

My guess after these few trials is that the 3 methods are roughly
equivalent in timing. divb might be marginally better, but not
substantially. I also guess that the series of polynomials might do
better in storage. (Hence the int overflow encountered in divb)
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#StableConversions100806
Oct_08_2006

Looks like divb stops working somewhere in base 15. I killed it after 11
hours or so of run time. Don't know what happens to it, but it stops
producing output after this line...
1, 8, 8, 7, 6, 6, 7, 0, ::> 0, 15, 15, 15, 15, 15, 15, 15, |268435455::> 268435455

Must be overflowing some field or another.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Killed_divb100806
Oct_08_2006

On my other computer, meanwhile... this week-end I ran over 75,000,000
base conversions from base 134 to base 135, using the multiply by pascal's
triangle's inverse method. All 75 million conversions were checked by
multiplying out the starting and ending polynomials. They all matched.
That's enough for me. I killed it dead. (the program, not the computer : -)

That data's gone, but anyone can repeat it using the pascalb.cpp program
linked earlier...
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/pascalb.cpp.txt

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#B134Conversions100806
Oct_07_2006

At base 13, I modified
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/coeff.cpp.txt
-to-
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/coeff2.cpp.txt

Replacing the repeated multiplications with variables.

Killed the first trial during base 13. Removed pascalb. Added coeff2.
Here are the new results.

http://taz.cs.wcupa.edu/~spalmer/PTIConvert/BCompareResults2.txt
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Simplified100706
Oct_07_2006

There are 3 similar programs here now...
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/coeff.cpp.txt
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/divb.cpp.txt
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/pascalb.cpp.txt

Here's how long they take to run on the school computer for various bases...
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/BCompareResults.txt

Nothing conclusive, but it looks like the pre-filled polynomials may be
roughly comparable with div/remainder. Naive matrix multiplication seems
much slower. That's not a surprise. As I'm writing this, it's up to base
8. It'll run 'til base 20 or 'til it gets killed for being a CPU hog.

coeff.cpp: Uses prebuilt polynomials to convert bases.
divb: Uses the divide / remainder method.
pascalb.cpp: Uses naive matrix multiplication.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Compare100706
Oct_06_2006

I wrote a quick shell script to run multiple bases in series. It uses
pascalb to compare pre and post values from the matrix multiplication
method of base conversion. It has checked 1 to 8 digits in bases 2
through 9. So far, all answers matched. i.e. all conversions were valid.
I guess base 10 will finish while I sleep. It's set to stop at 10 'cause
it's probably getting close to overflowing the int type.

That's 2^8 + 3^8 + 4^8 + 5^8 + 6^8 + 7^8 + 8^8 + 9^8 total matches and no
mismatches so far. Not proven, but pretty solid experimental evidence. If
you look at the code, you will see that a mismatch would've generated
return code -1 (255). The 0's show success.

[spalmer@taz cpp]$ ./run10.sh | tee run10.log
Running pascalb for base 2 - Return code: 0
Running pascalb for base 3 - Return code: 0
Running pascalb for base 4 - Return code: 0
Running pascalb for base 5 - Return code: 0
Running pascalb for base 6 - Return code: 0
Running pascalb for base 7 - Return code: 0
Running pascalb for base 8 - Return code: 0
Running pascalb for base 9 - Return code: 0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#GoodAnswer100606
Oct_05_2006

Here's a C++ program to convert (ordinal values for) 1 to 8 digits in any
base to the next higher base, doing matrix multiplication by the
right-bottom-rooted Pascal's Triangle's Inverse.
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/pascalb.cpp.txt

And here's it's output, it ran as "pascalb 2", converting base 2 to base 3.
http://taz.cs.wcupa.edu/~spalmer/PTIConvert/B2toB3byMatrixMultiplication.txt
Base_2 digits are to the left of the "::>" and base_3 numerals are to
the right.

It compiles under g++. To convert from/to different bases, just change
the command line argument.

To increment by more than one at a time, the PTI matrix would need to be
raised to the appropriate power. As already mentioned, that can be done here:
http://wims.unice.fr/wims/wims.cgi?session=USE594D0D4.2&+lang=en&+module=tool%2Flinear%2Fmatrix.en

The code's still sloppy, but it'll do for now.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PTIConvert100506
Oct_05_2006

Here's a question I don't think I could've begun to answer with any
confidence a couple weeks ago. Now, it's pretty simple to make a
conjecture with pretty high confidence. (base conversion by matrix
multiplication needs to be proved to make this answer certain)

==
Q: For some integer N, list the first C numerals whose result is
independent of base when converting from base B to base B+1, so long as B
is N or greater.
==

An example is N=2, C1=1. 1_B goes to 1_(B+1) when converting from any
base, B to B+1 as long as B is 2 or greater.

Another example, as noted before is N=10, Cj=189. 189_B goes to 162_(B+1)
in any base that's 10 or greater.

The test, now, is simply to compare the result of matrix multiplication
against the result from LegalD. If LegalD doesn't change anything in base
N, then it won't change anything in any base higher than N. Any digit
that's legal in N is legal in all higher bases.

This is alot harder to type than it is to think. Hope I explained it OK.

There's potential for a bunch of new integer sequences I think.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#YetOneMoreQuestion100506
Oct_04_2006

Another question I've been thinking about, but haven't had time to look
into...

I'm starting to think that multiplying a polynomial by a power of Pascal's
triangle's inverse is going to prove to be slower than the traditional
base conversion method for a single numeral. Not much reason for thinking
so, but that's what my gut's telling me.

Even if that's the case, however, what about converting multiple numerals?
I think I can construct a matrix of polynomials in base B, multiply the
matrix by a power of Pascal's triangle's inverse, and get back a matrix of
polynomials in B+1.

i.e. If I do the matrix multiplication of:***

|1,2,3,4,5| |1,-4, 6,-4, 1|
|2,3,1,4,5| |0, 1,-3, 3,-1|
|3,4,2,3,4| x |0, 0, 1,-2, 1|
|2,3,1,1,9| |0, 0, 0, 1,-1|
|1,1,1,1,1| |0, 0, 0, 0, 1|


It should convert 12345_B, 23145_B, 34234_B, 23119_B, and 11111_B all into
base (B+1) polynomials that are ready for processing by LegalD to make
them into numerals in a base B+1 number system.

I ran that multiplication through here.
http://wims.unice.fr/wims/wims.cgi
It gave back
1,-2,3,0,3
2,-5,4,3,1
3,-8,8,-1,2
2,-5,4,0,8
1,-3,4,-2,1

I passed those through LegalD and compared to traditional base conversion.
All matched. So it seems we can convert as many numerals as we want in a
single matrix multiplication, so long as I have the right sized
conversion-matrix.

If matrix multiplication can't do one numeral faster than the
division/remainder method, it still might be able to do lots of them
faster. There may be economies of scale which aren't available to the
division/remainder method. Don't know. Just another thing to check into.

***Note the placement of the zero's in the second matrix. I finally got
around to figuring out which way the matrix is supposed to face. That
one's right. All previous matrix orientations for the inverse Pascal's
triangle have been wrong.*

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AnotherQuestion100406
Oct_04_2006

Not surprisingly, it seems to work....

(* Multiply by (Pascal's_Triangle's_inverse)^6 *)
- up6(1,3,4,5,6);
up6(1,3,4,5,6);
val it = [1,~21,166,~583,768] : int list

(* Make digits legal in base 16 *)
- LegalD(0,0,0,1,~21,166,~583,768,16);
LegalD(0,0,0,1,~21,166,~583,768,16);
val it = [0,0,0,0,3,4,9,0] : int list

(* Compare to 'traditional' base conversion. *)
- B2B("13456",10,16,true);
B2B("13456",10,16,true);
val it = "3490" : string

And here's up6...

fun up6 (v, w, x, y, z) =
v ::
w - (24 * v) ::
x + (216 * v) - (18 * w) ::
y - (864 * v) + (108 * w) - (12 * x) ::
[z + (1296 * v) - ( 216 * w ) + (36 * x) - (6 * y)];


It still amazes me that you don't need to know the base until you're
figuring out the digits. I guess it shouldn't be a surprise though, since
it's really only true for this implementation. These parameters are
ordinal values, not digits. You would still need to know the base if the
parameters were actually digits.

I do think it's pretty cool, whether it's fast or not, direct conversion
from base 10 to base 16. I can't really claim it's division-free.
LegalD is essentially just div and mod implemented by hand. These
coefficients will get pretty big, so that might get slow. I wonder if it
could be improved by taking the coefficients mod the base before
multiplying the matrices. That might be a stretch.

No matter how much I figure out, I've always got more questions than
answers.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#B10toB16PascalTriangle100406
Oct_04_2006

Here's Pascal's Triangle's inverse to the 6th. When I get time, I'll make
an "up6" function using these coefficients, then pass that through LegalD
and compare against base10 to base16 conversion results.

http://wims.unice.fr/wims/wims.cgi?session=W05302B843.2&lang=en&cmd=reply&module=tool%2Flinear%2Fmatmult.en&matA=1%2C0%2C0%2C0%2C0%0D%0A-4%2C1%2C0%2C0%2C0%0D%0A6%2C-3%2C1%2C0%2C0%0D%0A-4%2C3%2C-2%2C1%2C0%0D%0A1%2C-1%2C1%2C-1%2C1&matB=1%2C0%2C0%2C0%2C0%0D%0A-4%2C1%2C0%2C0%2C0%0D%0A6%2C-3%2C1%2C0%2C0%0D%0A-4%2C3%2C-2%2C1%2C0%0D%0A1%2C-1%2C1%2C-1%2C1&show=A%5E6



Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#100406
Oct_04_2006

http://wims.unice.fr/wims/wims.cgi?session=W05302B843.2&+lang=en&+module=tool%2Flinear%2Fmatrix.en
http://wims.unice.fr/wims/wims.cgi?session=W05302B843.1&+lang=en&+module=tool%2Flinear%2Fmatmult.en

So I notice two things....
1.) Reversing the digits of a number is the same as multiplying it by a
matrix with the opposite diagonal of the identity matrix...

ie. Switching 196 to 691, is the same as multiplying

[1 9 6] by [0 0 1]
[0 1 0]
[1 0 0]


2.) I bet I can convert base B to base B+n by multiplying by Pascal's
triangle's inverse to the (n)th power, then legalizing the digits.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#LychrelMatrix100406
Oct_03_2006

Well, I do think what I found was the result of a matrix multiplication.
I think it goes something like this example, multiplying a 1x5 matrix by a
5x5 matrix to get a 1x5 matrix.

# Digits of a numeral
N = [V, W, X, Y, Z]

# Pascal's triangle's inverse
P = [
1 0 0 0 0
-4 1 0 0 0
6 -3 1 0 0
-4 3 -2 1 0
1 -1 1 -1 1
]

#
# Matric Multiplication goes something like this.
# (Since I've got Pascal's triangle's inverse sideways, I think I
# did the multiplication sideways too).
#
NP=[V[1 -4 6 -4 1] W[0 1 -3 3 -1] X[0 0 1 -2 1] Y[0 0 0 1 -1] Z[0 0 0 0 1]]

=[(1V) (-4V + 1W) (6V -3W +X) (-4V + 3W -2X +Y) (V - W + X - Y + Z)]

If each cell in NP is a digit, that matches the rule from this post...
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FiveDigits100106

That was when I was working out 5 digit numerals. So apparently, I've
found a matrix product without realizing it. That might be bad 'cause it
makes this method slow.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Followup100306
Oct_03_2006

OK. So a matrix and its inverse are two matrices which give the identity
matrix (I) when multiplied together. So if I'm reading AT&T right, that
means that [Pascal's_triangle] X [the_base_conversion_coefficients] = I.
I'm really stretching my memory cells, but I think an identity matrix is
square, with all 0's except the diagonal from top-left to bottom right.
If I recall correctly, that diagonals get 1's.

So the 2x2 identity matrix, if I remember right is..
1 0
0 1

And 3x3 is
1 0 0
0 1 0
0 0 1

And so on...

I think if you multiply a matrix by its identity matrix, you get back the
original matrix. (AI = A)

So, for some finite number of rows, call Pascal's triangle P and the base
conversion coefficients B and the identity matrix I.

Then PB = BP = I.

I think that's what that little snippet from AT&T meant.

LegalD makes perfect sense now. He's not doing anything to the value of
the polynomial. He's just making change. Give me B 1's and I'll give you
a B. Give me B B's and I'll give you a B^2. etc... There's nothing
tricky going on there.

It's still not clear to me why up1 works though. Why would multiplying a
polynomial in powers of X by Pascal's triangle's inverse convert it to an
equivalent polynomial in (X+1)? (and is that really what I'm doing? I
suspect I am, but I haven't confirmed that up1 is fundamentally just
multiplying a polynomial by a matrix).

Lots about "Pascal's triangle" on the web, but nothing useful could I find
about "Pascal's triangle" and "base conversion".

Side-note... Now that I'm thinking in the context of matrix
multiplication, if I get around to it, maybe Strassen's algorithm can make
the base conversion a tiny bit faster.

Incidentally, I noticed that the rows of Pascal's triangle add up to
consecutive powers of 2. I'm certain I'm not the first person who ever
noticed that, but it's pretty cool anyway.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MatrixInverse100306
Oct_03_2006

Not only have a stumbled onto palindromes again, but I've stumbled onto
Pascal's triangle again. I didn't even notice that. These entries both
involve stumbling onto Pascal's triangle...

(x+1) to a power:
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#X_plus_1_poly092006

Base conversion from base B to base B+1
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Phew100106

Only the signs are different. For base conversion, the '+' and '-' signs
alternate. For (X+1)^[power], they're all positive.

I think I'll have to read about the "binomial coefficient"...
http://en.wikipedia.org/wiki/Binomial_coefficient.

And AT&T says:
http://www.research.att.com/~njas/sequences/A007318
> If thought of as an infinite lower triangular matrix, inverse begins:
>
> +1
> -1 +1
> +1 -2 +1
> -1 +3 -3 +1
> +1 -4 +6 -4 +1

Rings a bell, but I don't quite remember what that means. However, here
are my coefficients up to 8 digits...
1
-7 1
21 -6 1
-35 15 -5 1
35 -20 10 -4 1
-21 15 -10 6 -3 1
7 -6 5 -4 3 -2 1
-1 1 -1 1 1 1 -1 1

Turn AT&T's list sideways and you've got mine.

So it seems that base conversion to one base higher is somehow related to
the inverse of Pascal's triangle.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PascalTriangle100306
Oct_02_2006

While I was at work today, my laptop was connected to the school computer
and running more comparisons. They looked at somewhere around half a
million numerals before the network went away. All of the base
conversions by digit transformations matched the divide/remainder base
conversions. I'm convinced.

I've never understood fourier transformations (or maybe I did 17 years
ago...Lots of dead brain cells since Numerical Analysis and Linear
Algebra classes), but I'm wondering if this base conversion method is
something like one of those. I sure wish I could find a web page to
describe fourier transformations in a language that resembles English.
I looked them over on wikipedia today, but it's not written to be
understood by someone who doesn't already understand them.

I think I need to find "wikipedia for children." ; -)
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreResults100206
Oct_02_2006

I ran a couple hours worth of base conversions of random numbers going
from base 5 -> 6 or 7 -> 8 this morning, in chunks of 80,000 at a
time.

Conversions by the divide/remainder method consistently took somewhere
around 7' 15". Conversions by the digit transformation method discussed
earlier took roughly 5' 15". Roughly 30% better or 1.5 ms per conversion.

However, this is absolutely not conclusive. There's alot of other stuff
going on that might be confounding those results. Checking for leading
0's, converting array indices to digit-values, generating random numbers.
The digit to value methods are different between the 2 functions I tested
and only the "traditional" method was doing the leading-0 check.

Also, I noticed that the performance of the digit transformation method
can be, roughly doubled, since each column of coefficients is a palindrome
(*palindromes again* :- ). One calculation could provide a pair of
coefficients.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SpeedResults100206
Oct_02_2006

Compared results from traditional base conversion for 40,000 random 8
digit, base 9 -> 10 conversions and 20,000 each of random 8 digit
conversions from, base 6 -> 7, base 7 -> 8 and base 8 -> 9.
All conversions performed by the digit transform method matched the
ones performed by the traditional method. No discrepancies were observed.

I'm satisfied with the validity of the transformation. I still need to
determine if it's any faster than the traditional way. For what it's
worth, 20,000 of each ran as follows.
Transform method: 1 minute, 8.9 seconds.
Divide method: 1 minute, 41.9 seconds.

That's not even close to conclusive, though. Neither program is
optomized and they were run in a shell generating random numbers as
it went. Who knows how much time was spent doing what?

Just for fun, here are a handful of the outputs...

Transform result: 02391698 Divide result: 02391698 same
Transform result: 34927889 Divide result: 34927889 same
Transform result: 22442548 Divide result: 22442548 same
Transform result: 11061004 Divide result: 11061004 same
Transform result: 01927314 Divide result: 01927314 same
Transform result: 01255587 Divide result: 01255587 same
Transform result: 12429982 Divide result: 12429982 same
Transform result: 08190180 Divide result: 8190180 same
Transform result: 10288642 Divide result: 10288642 same
Transform result: 09751000 Divide result: 9751000 same
Transform result: 34308254 Divide result: 34308254 same
Transform result: 21600005 Divide result: 21600005 same
Transform result: 00371149 Divide result: 00371149 same
Transform result: 26946402 Divide result: 26946402 same

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TestResults100206
Oct_01_2006

And the 8 digit functions seem to have worked on the first try! Now I
think I'm back where I thought I was before. Just a coding problem
remains. Generalize up1 and LegalD, then compare lots and lots of results
against B2B.

I'm not gonna bother pasting the current up1, since I just posted the 7
digit one. The 8 digit up1 exactly matches the conjecture which I just
posted. Here are a few samples, seeds selected at a whim...

# 11111111_10 -> 62A9A40_11
(* up1 convets from polynomial in X to polynomial in X+1 *)
- up1(1,1,1,1,1,1,1,1);
val it = [1,~6,16,~24,22,~12,4,0] : int list
(* LegalD makes the digits legal in a base X+1 number system *)

- LegalD(1,~6,16,~24,22,~12,4,0,11);
val it = [0,6,2,10,9,10,4,0] : int list
(* 10 -> A, 11 -> B, 12 -> C, etc... *)
(* "it" above and "it" below better match *)

- B2B("11111111",10,11,true);
val it = "62A9A40" : string


# 12345678_9 -> 6053444_10
(* up1 convets from polynomial in X to polynomial in X+1 *)
- up1(1,2,3,4,5,6,7,8);
val it = [1,~5,12,~16,14,~6,4,4] : int list

(* LegalD makes the digits legal in a base X+1 number system *)
- LegalD(1,~5,12,~16,14,~6,4,4,10);
val it = [0,6,0,5,3,4,4,4] : int list

(* "it" above and "it" below better match *)
- B2B("12345678",9,10,true);
val it = "6053444" : string

# 98764321_11 to 53A83A98_12
(* up1 convets from polynomial in X to polynomial in X+1 *)
- up1(9,8,7,6,4,3,2,1);
val it = [9,~55,148,~224,205,~112,34,~4] : int list

(* LegalD makes the digits legal in a base X+1 number system *)
- LegalD(9,~55,148,~224,205,~112,34,~4,12);
val it = [5,3,10,8,3,10,9,8] : int list

(* 10 -> A, 11 -> B, 12 -> C, etc... *)
(* "it" above and "it" below better match *)
- B2B("98764321",11,12,true);
val it = "53A83A98" : string

# 32112237_12 to 1A744C23_13
(* up1 convets from polynomial in X to polynomial in X+1 *)
- up1(3,2,1,1,2,2,3,7);
val it = [3,~19,52,~79,73,~41,15,3] : int list

(* LegalD makes the digits legal in a base X+1 number system *)
- LegalD(3,~19,52,~79,73,~41,15,3,13);
val it = [1,10,7,4,4,12,2,3] : int list

(* 10 -> A, 11 -> B, 12 -> C, etc... *)
(* "it" above and "it" below better match *)
- B2B("32112237",12,13,true);
val it = "1A744C23" : string

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#EightDigits100106
Oct_01_2006

Phew. I thought I hit a wall at seven digits, but finally I rearranged
things and saw a pattern. I think I'm back on track now... I've got
another conjecture for a general form for base conversion from base b to
base b+1.

With six digits, it was easy to find coefficients that made it work, but
hard to see a pattern. With 7 digits, until I reorganized things, I
wasn't even finding coefficients that worked consistently. The ones I
have now seem to work and I like the visible pattern, so I feel good about
them. Testing has still been light though. Lots of margin for error.

LegalD is unchanged except 2 more if blocks to handle the new digits.
(that needs to be made general). I'm not gonna bother pasting that in
again. A monkey could update it from yesterday's post to insert the 2 new
digits. Here's the latest 7 digit up1 function in SML/NJ...


fun up1 (t, u, v, w, x, y, z) =
t ::
u - (6 * t) ::
v + (15 * t) - (5 * u) ::
w - (20 * t) + (10 * u) - (4 * v) ::
x + (15 * t) - (10 * u) + (6 * v) - (3 * w) ::
y - (6 * t) + (5 * u) - (4 * v) + (3 * w) - (2 * x) ::
[z + t - u + v - w + x - y];


So my guess to build the 8 digit conversion from a polynomial in B to a
polynomial in B+1 now is

(s, t, u, v, w, x, y, z) ->
(s,
t - (7 * s),
u + (21 * s) - (6 * t),
v - (35 * s) + (15 * t) - (5 * u),
w + (35 * s) - (20 * t) + (10 * u) - (4 * v),
x - (21 * s) + (15 * t) - (10 * u) + (6 * v) - (3 * w),
y + (7 * s) - (6 * t) + (5 * u) - (4 * v) + (3 * w) - (2 * x),
z - s + t - u + v - w + x - y)


I don't like the way the multiplications are growing... I'm still
thinking it's gonna be more efficient than the traditional repeat-divide
and convert through an intermediary base, but I'm starting to wonder.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Phew100106
Oct_01_2006

Well, my conjecture was wrong... For 5 digits, it looks like the up1 rule
goes like this...


(V, W, X, Y, Z) ->
(V,
W - 4V,
X + 4V - 3W + 2V,
Y - 4V + 3W - 2X,
Z - Y + X -W + V)


My conjecture missed the +2V in the X' term, so now I'm back to the
drawing board for finding a general form... Here's ML that seems to be
working for 5 digits...


(*
* Convert numeral vwxyz to a polynomial over (x+1). First step
* in base conversion by digit transformation instead of division
* through an alternate base.
*)
fun up1 (v, w, x, y, z) =
v ::
w - (4 * v) ::
x + (4 * v) - (3 * w) + (2 * v) ::
y - (4 * v) + (3 * w) - (2 * x) ::
[z - y + x - w + v];

(*
* Convert a polynomail in B to a legal numeral
* in a base B number system.
*)
fun LegalD (V, W, X, Y, Z, B) =
if ( Z < 0 ) then
LegalD (V, W, X, Y-1, Z+B, B)
else
if (Z >= B) then
LegalD(V, W, X, Y+1, Z-B, B)
else
if ( Y < 0 ) then
LegalD(V, W, X-1, Y+B, Z, B)
else
if ( Y >= B ) then
LegalD(V, W, X+1, Y-B, Z,B)
else
if ( X < 0 ) then
LegalD(V, W-1, X+B, Y, Z, B)
else
if ( X >= B ) then
LegalD(V, W+1, X-B, Y, Z, B)
else
if ( W < 0 ) then
LegalD( V-1, W+B, X, Y, Z, B)
else
if ( W >= B ) then
LegalD (V+1, W-B, X, Y, Z, B)
else
V :: W :: X :: Y :: [Z];


(*
* A sample run and comparison to traditional base conversion.
*)
# Polynomial in Base to polynomial in Base+1
- up1(7,1,9,7,6);
val it = [7,~27,48,~36,14] : int list

# Convert to equivalent polynomial with legal digits in a
# base 13 number system.
- LegalD(7,~27,48,~36,14,13);
val it = [5,2,6,4,1] : int list

#
# For comparison, convert 71976 from base 12 to 13 by going
# through base 10 as an intermediate.
#
- B2B("71976",12,13,true);
val it = "52641" : string

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FiveDigits100106
Sep_30_2006

OK... So I had to try it... In 1 example, it worked. I ran 8 consecutive
up1's over 777_8, then 1 LegalD. It got 1[15][15]_16 correct. For
whatever that's worth.

# Start with 777_8
- up1(0,7,7,7); # 8 -> 9
val it = [0,7,~7,7] : ?.int list
- up1(0,7,~7,7); # 9 -> 10
val it = [0,7,~21,21] : ?.int list
- up1(0,7,~21,21); # 10 -> 11
val it = [0,7,~35,49] : ?.int list
- up1(0,7,~35,49); # 11 -> 12
val it = [0,7,~49,91] : ?.int list
- up1(0,7,~49,91); # 12 -> 13
val it = [0,7,~63,147] : ?.int list

- LegalD(0,7,~63,147,13); # Make digits legal
val it = [0,3,0,4] : ?.int list

- B2B("777",8,13,true); # Compare to traditional base convert...
val it = "304" : string

- up1 (0,7,~63,147); # 13 -> 14 (illegal digits again)
val it = [0,7,~77,217] : ?.int list
- up1 (0,7,~77,217); # 14 -> 15
val it = [0,7,~91,301] : ?.int list
- LegalD(0,7,~91,301,15); # Make digits legal
val it = [0,2,4,1] : ?.int list

- B2B("777",8,15,true); # Compare to traditional base conversion
val it = "241" : string

- up1(0,7,~91,301); # One more, just for fun. B16 (illegal again)
val it = [0,7,~105,399] : ?.int list
- LegalD(0,7,~105,399,16); # Make legal again.
val it = [0,1,15,15] : ?.int list
- B2B("777",8,16,true); # Compare to traditional base convert.
val it = "1FF" : string

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Up1Repeated093006
Sep_30_2006

Couldn't pull myself away... It occurred to me that the >B and < 0 rules
served no purpose except to make the digits legal in the number system.
The same logic should apply for all digits. Bad news- LegalD requires
looping or recursion over the length of the numeral. Good news- It seems
to work. ML functions up1 and LegalD seem to do base conversion from base
B to base B+1 for on any number up to 4 digits (I think). The logic for
both may be extensible to any sized numeral... Assuming my conjecture
earlier about extending the up1 rule is right.

fun up1 (w, x, y, z) =
w ::
x - 3 * w ::
y - (2 * x) + (3 * w) ::
[z - y + x -w];

fun LegalD (W, X, Y, Z, B1) =
(*
* B1 is the target base (from B to B1 := B+1).
*)
if ( Z < 0 ) then
LegalD (W, X, Y-1, Z+B1, B1)
else
if (Z >= B1) then
LegalD(W, X, Y+1, Z-B1, B1)
else
if ( Y < 0 ) then
LegalD(W, X-1, Y+B1, Z, B1)
else
if ( Y >= B1 ) then
LegalD(W, X+1, Y-B1, Z,B1)
else
if ( X < 0 ) then
LegalD(W-1, X+B1, Y, Z, B1)
else
if ( X >= B1 ) then
LegalD(W+1, X-B1, Y, Z, B1)
else
W :: X :: Y :: [Z];

I'm not entirely sure I've got all the cases, but I've got a good number
of them I think.... Hopefully, now it's just a coding problem... I don't
think I'll bother with a proof. Someone's probably already done it. I'll
be happy if I can verify it experimentally.

(*
* up1 followed by LegalD transforms digits from 0322_6 to 0233_7.
* Traditional base conversion from B2B gets the same.
*)
- up1(0,3,2,2);
val it = [0,3,~4,3] : int list
- LegalD(0,3,~4,3,7);
val it = [0,2,3,3] : int list
- B2B("0322",6,7,true);
val it = "0233" : string

(*
* up1 followed by LegalD transforms digits from 9845_11 to 7630_12.
* Traditional base conversion from B2B gets the same.
*)
- up1(9,8,4,5);
val it = [9,~19,15,0] : int list
- LegalD(9,~19,15,0,12);
val it = [7,6,3,0] : int list
- B2B("9845",11,12,true);
val it = "7630" : string

(*
* up1 followed by LegalD transforms digits from 7251_7 to 4747_8.
* Traditional base conversion from B2B gets the same.
*)
- up1(7,2,5,1);
val it = [7,~19,22,~9] : int list
- LegalD(7,~19,22,~9,8);
val it = [4,7,4,7] : int list
- B2B("7251",7,8,true);
val it = "4747" : string

(*
* up1 followed by LegalD transforms digits from 9999_11 to 7760_12.
* Traditional base conversion from B2B gets the same.
*)
- up1(9,9,9,9);
val it = [9,~18,18,0] : int list
- LegalD(9,~18,18,0,12);
val it = [7,7,6,0] : int list
- B2B("9999",11,12,true);
val it = "7760" : string

(*
* up1 followed by LegalD transforms digits from 9847_106 to [8][88][15][2]_107.
* Traditional base conversion from B2B gets the same.
*)
- up1(9,8,4,7);
val it = [9,~19,15,2] : int list
- LegalD(9,~19,15,2,107);
val it = [8,88,15,2] : int list
- B2B("9847",106,107,true);
val it = "8/F2" : string
- B2B("/",107,10,true);
val it = "88" : string
- B2B("F",107,10,true);
val it = "15" : string

No failures observed yet. As I said. I think now it's a coding
problem... Time to play : -)

Hmmm... up1 is fast. LegalD is slower. I wonder if I could do up1
multiple times to convert over more than just B to B+1, then just apply
LegalD at the ultimate destination. Maybe that wouldn't be any faster
anyway, since LegalD would probably have more work to do at the end.
Dunno... That's a question for another day.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#GotItIThink093006
Sep_30_2006

Looks like the scrub-Y and scrub-Z rules are similar for 3 and 4 digits.
Still need to work out negative digits in the X position. Here are ML
functions for the first 3 rules in 4 digits...

fun up1 (w, x, y, z) =
w ::
x - 3 * w ::
y - (2 * x) + (3 * w) ::
[z - y + x -w];

fun ScrubZ(W,X,Y,Z,B) =
if (Z < 0) then
W :: X :: Y-1 :: [B+Z+1]
else
W :: X :: Y :: [Z];

fun ScrubY(W, X, Y, Z, B) =
if (Y < 0) then
W :: X-1 :: B+Y+1 :: [Z]
else
W :: X :: Y :: [Z];

(*
* Sample execution, compare to traditional base conversion.
*)

(* 1464 -> 1111 in any base *)
- up1 (1,4,6,4);
val it = [1,1,1,1] : int list
- B2B("1464",73,74,true);
val it = "1111" : string

(* 1462_10 -> 110A_11 *)
- up1 (1,4,6,2);
val it = [1,1,1,~1] : int list
- ScrubZ(1,1,1,~1,10);
ScrubZ(1,1,1,~1,10);
val it = [1,1,0,10] : int list
- B2B("1462",10,11,true);
val it = "110A" : string

(* 2828_12 -> 216C_13 *)
- up1(2, 8, 2, 8);
val it = [2,2,~8,12] : int list
- ScrubY(2,2,~8,12,13);
val it = [2,1,6,12] : int list
- B2B("2828",13,14,true);
val it = "216C" : string

Oh. I just noticed I have to do something in the first rule about cases
where z - y + x - w is bigger than the base. It can put out illegal
digits that need handling... 2828_10 would be an example of this. I guess
that needs to become (2,2,~7,12-B) instead of (2,2,~8,12) in any base
where there is no 12 digit.

Gotta go. I'll be back tomorrow I guess.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ScrubYZ093006
Sep_30_2006

Inserting 1464 into the 3 digit rule, gives a guess at the first 4 digit
rule. Also, the beginning of a pattern I think...

My *guess* is
(W, X, Y, Z) -> (W, X - 3W, Y - 2X + 3W, Z - Y + X - W)

I tried that guess on 28B8_B
(W,X,Y,Z) = (2,8,11,8)
W' = W = 2
X' = X - 3W = 2
Y' = Y - 2X + 3W = 1
Z' = Z - Y + X - W + W = 3
==> (2,2,1,3)

Then compared to traditional base conversion for 28B8_B where B = 12, 13,
14, 23. In in each of those bases, 28B8_B does in fact, go to 2213_(B+1)
as guessed.

I'm disappointed to see the amount of multiplication required increasing.
I had hoped to avoid that, but I'm not seeing a way.

I think there's enough of a pattern there to project rule 1 for an
arbitrary sized numeral, for example, I guess 4 digits to 5 digits will go
like this...

4 digits...
(W, X, Y, Z) ->
____(W, X - 3W, Y - 2X + 3W, Z - Y + X - W)

5 digits...
(V, W, X, Y, Z) ->
___(V, W - 4V, X - 3W + 4V, Y - 2X + 3W + 4V, Z - Y + X - W + V)

That is completely untested tough. I'll have to test it and
look at the subsequent negative digit rules later. Gotta get ready for
pre-schooler's swim lessons now.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AGuess093006
Sep_29_2006

Found a good one for 4 digits I think...

(1, 4, 6, 4) -> (1, 1, 1, 1)

I'll bet that one's not composite, 'cause as long as B is big
enough to have a 6 digit, B+1 has '1'. I don't need to know what B
is. 1464_B converts to 1111_(B+1) in every base I tried. A dozen
or more.

Also, by doubling it, (2,8,12,8) -> (2,2,2,2) once B gets biger than 12.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#OneFourSixFour092906
Sep_29_2006

Inserted a typo into the 2 digit rule when I was trying to make the
variables consistent between 2 and 3 digits. Here are, I hope, the
correct rules...

2 digits
(Y, Z) && (Z >=0) -> (Y, (Z-Y))
(Y, Z) && (Z < 0) -> ((Y-1), B-|Z|+1)

3 digits
(X, Y, Z) -> (X, Y - 2X, Z - Y + X)
(X, Y, -Z) -> (X, Y-1, B-|Z| + 1)
(X, -Y, Z) -> (X-1, B-|Y| + 1, Z)

It's handy that with the typo fixed, if X=0 in the 3 digit rules, the X
seems to drop out nicely and the 3 digit rules become the 2 digit rules.

(0, X, Z) -> (Y - 2(0), Z - Y + 0) -> (Y, Z-Y)
(0, Y, -Z) -> (0, Y-1, B-|Z|+1) -> (Y-1, B-|Z|+1)
(0, -Y, Z) -> # Not considering negative numbers for now.

So from 5, we're down to 3 general rules for converting 2 and 3 digit
numbers from base B to base B+1. Don't forget, there might still be some
unfilled gaps though.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AnotherTypo092906
Sep_28_2006

First 4 digit rule...
(1,1,1,1) -> (0,B-1,2,0)

Must be a composite transformation.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FourDigitsUp1092806
Sep_28_2006

I had a typo in the 3 digit scrub Y rule. Here's a rule summary of what I
think I've observed so far. Base conversion from base B to base B+1 for 2
and 3 digits.

2 digits
(Y, Z) && (Z >=0) -> (Z, (Z-Y))
(Y, Z) && (Z < 0) -> ((Y-1), B-|Z|+1)

3 digits
(X, Y, Z) -> (X, Y - 2X, Z - Y + X)
(X, Y, -Z) -> (X, Y-1, B-|Z| + 1)
(X, -Y, Z) -> (X-1, B-|Y| + 1, Z)

As mentioned yesterday, this may not be complete yet, but it's a pretty
good start. Guess I'll have to code something to check 10 through 999 and
compare them against the traditional conversion to flush out the gaps.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#RuleSummary3Digs092706
Sep_27_2006

Here are 3 general rules which seem to work for 3 digit base conversions
from base B to base B+1 (after very very very brief testing).

(X, Y, Z) -> (X, Y - 2X, Z - Y + X)
(X, Y, -Z) -> (X, Y-1, B-|Z| + 1)
(X, -Y, Z) -> (X, B-|Y| + 1, Z)

And here are some ML functions which implement them...

fun up1 (x, y, z) = x :: y-2*x :: [z-y+x];

fun ScrubZ(X,Y,Z,B) =
if (Z < 0) then
X :: Y-1 :: [B+Z+1]
else
X :: Y :: [Z];

fun ScrubY(X,Y,Z,B) =
if (Y < 0) then
X-1 :: B+Y+1 :: [Z]
else
X :: Y :: [Z];

Seems to me a good order is up1, then ScrubZ on the result, then ScrubY on
that result. I'm sure I've still got stuff falling through the cracks,
but it's working a little. Here are a few test cases...

(*
* Test case: 342_7 to 261_8, up1 and ScrubY.
* Compare to "traditional" base conversion from B2B.
*)
- up1(3,4,2);
val it = [3,~2,1] : int list
- ScrubY(3,~2,1,7);
val it = [2,6,1] : int list
- B2B("342",7,8,true);
val it = "261" : string

(*
* Test case 194_13 to 16A_14 by up1 and ScrubZ.
* Compare to "traditional" base conversion from B2B.
*)
- up1(1,9,4);
val it = [1,7,~4] : int list
- ScrubZ(1,7,~4,13);
val it = [1,6,10] : int list
- B2B("194",13,14,true);
val it = "16A" : string

(*
* Test case 484_AnyBase to 400_AnyBase+1 [AnyBase >8]
* No scrubbing necessary. Just up1. Compare to 2 "traditional"
* base conversion B2B calls to sample different bases.
*)
- up1(4,8,4);
val it = [4,0,0] : int list
- B2B("484",10,11,true);
val it = "400" : string
- B2B("484",57,58,true);
val it = "400" : string

(*
* Test case 400_11 to 344_12. up1 and ScrubY compared to B2B
*)
- up1(4,0,0);
val it = [4,~8,4] : int list
- ScrubY(4,~8,4,11);
val it = [3,4,4] : int list
- B2B("400",11,12,true);
val it = "344" : string

So it seems I've got the broad strokes done for division-free base
conversion from base B to base B+1 for 2 and 3 digits. The good news is
the number of rules isn't unmanageable either. I had to look at lots of
rules to find the general ones, but once they're general, there aren't
many of 'em. 2 rules for base 2, 3 rules for base 3. Maybe some more
special cases I haven't found yet.

I'm hoping to be able to reuse/modify these rules as the number of digits
For example, I've noticed that 189[d1][d2] goes to 162[d3][d4] just like
189 goes to 162 for 5 and 3 digit numbers, respectively. The same
principles must be at work causing that behavior. Maybe this'll enable
reapplying the same rules for higher numbers of digits.

I wonder if there's a name for base conversions which yield the same
result regardless of base. I think that's kind of cool... to be able to
convert bases for some numbers without knowing or caring what base I'm
starting or ending in. I wouldn't have guessed that capability is as
common as it seems.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CandidateRules3D092706
Sep_27_2006

Here are some rules for 3 digit numerals starting with 2...
(2, Y, Z) -> (2, Y-4, Z-Y+2)
(2, -Y, Z) -> (1, B-|Y| + 1, Z)
(2, Y, -Z) -> (2, Y-1, B-|Z|+1)
(2, 0, -Z) -> (1, B, B-|Z|+1)

which led to a general rule for 3 digit numbers..
(X, Y, Z) -> (X, Y - 2X, Z - Y + X)

I had hoped to avoid multiplication, but it looks like I need to multiply
for the 2X term in the second digit (unless I want to carry a look-up
table in memory, which I don't).

And an ML function to demonstrate...

- fun up1 (x, y, z) = x :: y-2*x :: [z-y+x];
val up1 = fn : int * int * int -> int list

- up1(3,6,5); (*** Digit transform ***)
val it = [3,0,2] : int list
- B2B("365",10,11,true); (*** Base conversion ***)
val it = "302" : string

- up1(4,8,7); (*** Digit transform ***)
val it = [4,0,3] : int list
- B2B("487",10,11,true); (*** Base conversion ***)
val it = "403" : string

- up1(4, 9, 5); (*** Digit transform ***)
val it = [4,1,0] : int list
- B2B("495", 10, 11, true); (*** Base conversion 10/11 ***)
val it = "410" : string
- B2B("495", 100, 101, true); (*** Base conversion 100/101 ***)
val it = "410" : string


Obviously, I chose those examples carefully. I still have to work out the
form for processing negative digit results, but I'm pretty sure this rule
can be the first step for all 3 digit numerals. Now I just need to
generalize the handling mechanism when Y and/or Z are negative. It seems
the base doesn't come into play unless you land on a negative digit after
this first rule. 495 will go to 410 in every single conversion from base
B to base B+1 (where 495 exists).

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#GenRule3Digits092706
Sep_27_2006

I think this is lisp for most of the 3 digit rules I've observed so far...
transformations from base B to base B+1 with numerals that begin with '1'
or numerals where the 1st and 2nd digit are the same. (The 3 identical
digits rules also seem to work for just 2 identical digits if they're the
first 2.)


(defun Scrub3 (X Y Z B)
"Account for negatives after 1st transformation"
(if (and (< Y 0) (= X 1))
(list (- X 1) (+ B 1 Y) Z)
(if (and (< Z 0) (= X 1))
(list X (- Y 1) (+ B Z))
(list X Y Z))))

(defun Up1 (X Y Z B)
"Transform XYZ_B to X'Y'Z'_(B+1)"
(if (equal X Y)
(list (- X 1) (+ 1 (- B Y)) Z '_ (+ B 1))
(if (equal X 1)
(append (Scrub3
1 (- Y 2) (- Z (- Y 1)) B) (list '_ (+ B 1)))
'("I don\'t know how to do that yet."))
)
)


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Combined3Digits092706
Sep_27_2006

Some more rules for 3 digit numbers going from base B to base B+1. These
for repeating digits...

(1,1,1) -> (0, B, 1)
(2,2,2) -> (1, B-1, 2)
(3,3,3) -> (2, B-2, 3)
(4,4,4) -> (3, B-3, 4)
(5,5,5) -> (4, B-4, 5)
(6,6,6) -> (5, B-5, 6)
(7,7,7) -> (6, B-6, 7)
...
...
...
(X,X,X) -> (X-1, B-X+1, X)

777_11 -> (7,7,7) -> (6,5,7) -> 657_12
- B2B("777",11,12,true);
val it = "657" : string

And a lisp function to perform the transformation...

(defun Up1 (X Y Z B)
"Transform XYZ_B to X'Y'Z'_(B+1)"
(if (and (equal X Y) (equal X Z))
(list (- X 1) (+ 1 (- B Y)) Z '_ (+ B 1))
(print "I don\'t know how to do that yet.")))

(Up1 7 7 7 11)
(6 5 7 _ 12)


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreRules3Digits
Sep_27_2006

Here are some rules for converting 3 digit numerals, starting with 1, from
base B to base (B+1).

(1,0,1) -> (0, B-1, 2)
(1,0,2) -> (0, B-1, 3)
(1,0,3) -> (0, B-1, 4)
...
(1,0,B-1) -> (0, B-1, B)
(1,1,1) -> (0, B, 1) -> (B,1)
(1,1,2) -> (0, B, 2)
(1,1,3) -> (0, B, 3)
...
(1,1,B-1) -> (0, B, B-1)
(1,2,0) -> (0, B, B)
(1,2,1) -> (1,0,0)
(1,X,Y) -> (1, X-2, Y - (X - 1))

*** ???????????? ****
(1,-1,Y) -> (0,B,Y)
(1,-2,Y) -> (0,B-1,Y+1)
*** ???????????? ****

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ThreeDigitRules092706
Sep_26_2006

So here's division-free base conversion to convert 2 digit numbers
from base B to base B+1 in some sloppy, ad-hoc notation. Looks kind
of like the rule notation for NIM or eliza from AI class last week. I
guess that's not surprising.

Base B....Base B+1
======....========
(1, 0) -> (B)
(1, N) -> (1, (N-1))

(2, 1) -> (1, B)
(2, 0) -> (1, (B-1))
(2, N) -> (2, (N-2))

(3, 2) -> (2, B)
(3, 1) -> (2, (B-1))
(3, 0) -> (2, (B-2))
(3, N) -> (3, (N-3))

(4, 3) -> (3, (B))
(4, 2) -> (3, (B-1))
(4, 1) -> (3, (B-2))
(4, 0) -> (3, (B-3))
(4, N) -> (4, (N-4))

(5, 4) -> (4, (B))
(5, 3) -> (4, (B-1))
(5, 2) -> (4, (B-2))
(5, 1) -> (4, (B-3))
(5, 0) -> (4, (B-4))
(5, N) -> (5, (N-5))

(i.e. 10_B always goes to digit B in base B+1, 19 goes to 18, 24 goes to
22, 22 goes to 20, 36 goes to 33, 56 goes to 51, 51 goes to 4X where
X=B-3, etc...)

And I think all that reduces to this...

Base B Base B+1
====== ========
(1, N) -> (1, (N-1))
(1, -N) -> (B)

(2, N) -> (2, (N-2))
(2, -N) -> (1, (B-|N|+1))

(3, N) -> (3, (N-3))
(3, -N) -> (2, (B-|N|+1)

(4, N) -> (4, (N-4))
(4, -N) -> (3, (B-|N|+1)

(5, N) -> (5, (N-5))
(5, -N) -> (4, (B-|N|+1)

...
...
...

And I think that further reduces to just 2 rules, to
be tried in sequence.

1.) (X, Y) && (Y >=0) -> (X, (Y-X))
2.) (X, Y) && (Y < 0) -> ((X-1), B-|Y|+1)
(* and optionally, drop the leading 0 *)
3.) (0, Y) -> (Y)

Here are some haphazzard examples...
74_10 -> (7,4) -> (7,-3) -> (6, 10-3+1) -> (6,8) -> 68_11
57_10 -> (5,7) -> (5,2) -> 52_11
51_10 -> (5,1) -> (5,-4) -> (4, 10-4+1) -> (4,7) -> 47_11
10_10 -> (1,-1) -> (10) -> A_11
31_10 -> (3,1) -> (3, -2) -> (2, 10-2+1) -> (2, 9) -> 29_11
11_10 -> (1,0) -> 10_11
99_14 -> (9,9) -> (9,0) -> 90_15
11_71 -> (1,1) -> (1,0) -> 10_72
22_71 -> (2,2) -> (2,0) -> 20_72
37_71 -> (3,7) -> (3,4) -> 34_72
FE_35 -> (F,E) -> (F,-1) -> (E,36-1+1) -> (E,Z) -> EZ_36
DD_19 -> (D,D) -> (D,0) -> D0_20
D7_16 -> (D,7) -> (D,-6) -> (C,16-6+1) -> (C,B) -> CB_17
R2_30 -> (R,2) -> (R,-25) -> (Q,30-25+1) -> (Q,6) -> Q6_31

Here are a few of those done the old fashioned way... They all check out.
- B2B("FE",35,36,true);
val it = "EZ" : string

- B2B("D7",16,17,true);
val it = "CB" : string

- B2B("R2",30,31,true);
val it = "Q6" : string

That's just 2 digits. I have a feeling it's gonna get worse before it
gets better.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#BaseConvertUpOne092606
Sep_20_2006

This is funny. It looks like the coefficients of the (x+1)^[power]
polynomials are all palindromes...

Power = coefficients...
0 = 1
1 = 1,1
2 = 1,2,1
3 = 1,3,3,1
4 = 1,4,6,4,1
5 = 1,5,10,10,5,1

And I'll bet 6 gets 1,6,15,20,15,6,1. Let's see... Yup. If I did it
right, that's what it got...

6 = 1,6,15,20,15,6,1
So if I speculate for the next few, I get

7 = 1,7,21,35,35,21,7,1
8 = 1,8,28,56,70,56,28,8,1
9 = 1,9,36,84,126,126,84,36,9,1

And I searched for that last one at AT&T and found Pascal's triangle...
http://www.research.att.com/~njas/sequences/?q=1%2C+9%2C+36%2C+84%2C+126%2C+126%2C+84%2C+36%2C+9%2C+1&language=english&go=Search

I guess this isn't the first time I've seen this. Just long since
forgotten... It's a funny coincidence. Can't seem to get away from
palindromes. I don't think these will be useful for b to b+1 base
conversion though. Getting from x^n to (x+1)^n still requires numerous
multiplications.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#X_plus_1_poly092006
Sep_20_2006

Noticed this while shaving this morning...

(x+1)^3 appears to be x^3 + x^2 + (x+1)^2 + x(x+1)

i.e.
11^3 =?= 10^3 + 10^2 + 11^2 + 10(11)
=1000 + 100 + 121 + 110
=1331

If I do the algebra,
(x+1)^3 and (x^3 + x^2 + (x+1)^2 + x(x+1)) both work out to be
x^3 + 3x^2 + 3x + 1.

So if I know x, x^2, x^3 (which I presumably do in positional notation) I
can calculate (x+1)^3 with just 1 multiplication. [Remembering that I already
know that (x+1)^2 is x^2 + x + x + 1]

Why do I care? I'm wondering about a division-free algorithm for
converting from base b to base (b+1). An algorithm like that might make
it faster to calculate all radix representations for a given number.

I suppose I could try to look it up somewhere, but it might be more fun to
figure it out...

This identity might be a step in the right direction so I thought I'd
write it down so I don't forget it.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#X_plus_1_cubed092006
Aug_10_2006

http://www.jasondoucette.com/worldrecords.html

Just read about the 196 problem in palindromes. Take a number, reverse
the digits, add the two together; repeat until you get a palindrome.
They've done 196 to huge numbers of digits and haven't found any. I
thought I'd try 196 in bases 8 and 16. They both become palindromes
quickly. In 8, 196 is 304. 304 + 403 is 707. In 16, 196 is C4. C4 + 4C
is 110, then 110 + 011 is 121.

One step for base 8. Two steps for base 16. Those are both powers of 2.
Base 2 is one step too. 2 * 5 is 10. I wonder if 196 in base 5 is
similar in difficulty to base 10...

Nope. If I did it right, 196 goes to 1241_5, which goes to 34243_5 in 4
additions.

1241
+1421
----
3212
+2123
----
10340
+04301
-----
20141
+14102
-----
34243

One step in base -10 too I think.
2(-10^2) + 1(-10) + 6
6(-10^2) + 1(-10) + 2
=======================
8(-10^2) + 2(-10) + 8

Curious...

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#OneNineSixLychrel081006
Aug_10_2006

So for numbers ending in 1, Nx + 1, we already knew that

(1,N-10,1)_-N is a palindrome.

It looks like
(1,2N-(N/2),1)_-2N is also a palindrome, at least for positive even bases.

Thus, as observed, since every decimal number ending in 1 has at least
these 2 palindromes, neither can appear in the "fundamental" palindrome
list.

So we know now that 10N + 1 is a palindrome as:
1.) 1, N - 10, 1 - base -N
2.) 1, 2N - (10/2), 1 - base -2N

(*Make sure you've got bases represented right. No mixing units. :*)

ex. 9057 = 21541_8

2154_8 = 1132_10
10_8 = 8_10
1132 - 8 = 1124

= 1,1124,1 base (-1132)
and

2154_8 = 1132_10 * 2 = 2264
10_8 / 2 = 4_10.
2265 - 4 = 2260

= 1,2260,1 base (-1164)

Here's the algebra for the 2nd one....
1, 2N - (10/2), 1 - base -2N (10_N = N_10 below)
=(-2N)^2 + (2N - (N/2))-2N + 1
=4N^2 - 4N^2 + (N/2)2N + 1
=4N^2 - 4N^2 + 2N^2/2 + 1
=N^2 + 1. (N_10 becomes 10_N again).
=10N + 1

Which is what we wanted to see. Thus, no numbers which end in 1 in any
positive even base (other than 11_N-1) have unique palindromes that are
not universal or odd. They all have at least 2.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOneFund080906
Aug_09_2006

Here are more in the series of fundamental palindromes and their primes.

19379: [19][3][19]_-32, 19379: **p 19378( 19377 / 19379 ) : 50: 4
20123: [23][20][23]_-30, 20123: **p 20122( 20121 / 20123 ) : 50: 4
20627: [2][85][2]_-125, 20627: **p 20626( 20625 / 20627 ) : 50: 4
23099: [11][47][11]_-48, 23099: **p 23098( 23097 / 23099 ) : 50: 4
25583: [8][25][8]_55, 25583: **p 25582( 25581 / 25583 ) : 59: 4

There are still no 1's at the end. Nothing is jumping out at me to
explain that yet. I already know they all have negative base palindromes
(July 24 and July 25).
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOnePals072406
I'm definitely willing to believe there's always a positive palindrome
too, although I haven't noticed it yet. If so, they would be excluded
from the fundamental palindrome list.

==
In the prime check, at 689441, the ratio of primes with palindromes that
are in the multiple class or higher is 55720 / 55772, 99.907%. The
highest twins so far are 663571 (1,0,2,0,2,0,1,0,2,0,2,0,1)_3, 670199
(8,0,7,0,8)_17, 670777 (8,0,9,0,8)_17 and 671933 (8,0,13,0,8)_17. All
identical.

Still 115 maximum palindromic representations. We found 673201 with 99,
680401 with 103, 600601 and 687971 with 105, 604801 with 106 and 617761
with 107. Those are the highest ones above 600000. I've also noticed that
numbers like 600601 seem somewhat common in the high palcount list, ie x+1
appended to x, which ends in 0.

It's kind of amazing to think this program has been running on my laptop
since July 18. Almost a month to get to 689441. I see patch Tuesday
might put an end to things soon though.

I could make this into a full time hobby. It's almost a shame I have to
work for a living. ;-). Now I'm thinking that it would be fun to compare
the prime densities of the fundamental palindromes egainst those of
Euler's equation (x^2 + x + 41) and the others I mentioned back on July 6.
http://mercury.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeCats070606

I really oughta be looking for better than naive, brute force algorithms
too.

I might not find time for all these things that "might be fun" until I
retire, if then.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Fundamentals080906
Aug_08_2006

I guess it should've been obvious. I've noticed this several times and
keep forgetting when I bump into it again. Of course list 1 is a list of
primes (after 9).

With the exception of perfect squares, like 9 in the fundamental
palindrome list; as a general rule, any time you find a number with
no 2-digit palindromes, you've found a prime.

I must remember that finding 2 digit palindromes is essentially the same
thing as finding factors from 2 through sqrt(N). Perfect squares are the
only numbers that don't have any. It looks like all x^2 above 9 have
(1,2,1) in bases x-1 and -(x+1).

Let's see...

::(1,2,1)_(x-1)
(x-1)^2 + 2(x-1) + 1 =
=x^2 -2x + 1 + 2x -2 + 1
=x^2

::(1,2,1)_-(x+1)
=(x+1)^2 - 2(x+1) + 1
=x^2 + 2x + 1 - 2x -2 + 1
=x^2

So the squares drop out of list 1, leaving just primes and 9.

So we see why 9 is a special case in list 1. It doesn't have (1,2,1) in
base 2, because there aren't enough digits to make 2. All other composites
drop out by the 2 digit palindromes or the perfect square palindromes.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#OfCourse080806
Aug_07_2006

So I'm thinking that what's needed is a tiered classification system for
the palindromes. Trivial & non-trivial just won't do. Something like:

Universal palindromes (every number has these):
(1)_N+1 and up.
(1,1)_N-1
(1,N-1,1)_-(N-1)

Odd & even
(1,((N-1)/2)-2,1)_((N-1)/2) :: Odd
(2,2)_((N/2)-1) :: Even

Prime Multiples
(x,x)_y for prime integers x and y >1.
(2,2) fits here too. It continues to be a spoiler.

Fundamentals
Palindromes that are none of the above and appear by themselves,
accompanied only by odd or universal palindromes.

Composed/Constructed
List of palindromes that only appear in the company of others. Composite
multiples go here. For example, (4,4) is composed, since finding (4,4)
implies I can also find (2,2).

Others? 2 digit, negative base palindromes remain unclassified, but I'm
too tired to think about it now. They'll wait.

Other others? Not that I've thought of so far. I'll have to do some web
searches to see if classifications like this have already been created.

==
So restating the prime lists in this context...

1.) Numbers with exactly 1, fundamental palindromic representation and
without a (2,2) representation will always be prime. Remains to be shown.

2.) Numbers with only universal and odd palindromic representations will
always be primes. Showed that earlier.

I also guess that both of those are infinite lists. That also remains to
be shown. Last, I'm seeing that none of 'em end in 1 pattern again in
list 1.) as in list 2...
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOne072506

I suppose that means that (1,k-10,1)_-k is a constructed palindrome, not a
fundamental one. I'm also not sure about that yet.

Side note/Silly diversion: I wonder how base negative unary works. How
'bout base 0? There's something unsettling in jumping straight from base
1 to base -2.

I was thinking maybe base -1 could have a digit that consumes a position
but has no value (not even 0). Say '_'. Then I could write -3 as 1_1_1
(or 1___1___1 or 1_1_111). Base 0 could have an infinite supply of
digits, but all numbers would be expressed in 1 digit. We might say,
then, that all bases are also base 0. Each numeral is a digit.:-)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Palclass080706
Aug_07_2006

Here are the palindromes with just 1 non-trivial palindromic
representation found during work today.... The **p in each line indicates
that these all matched my guess. They are prime. If they were composite,
it would say **c. The only composite thus far is still 9.

1439: [9][7][9]_-13, 1439: **p 1438( 1437 / 1439 ) : 24: 4
1907: [3][16][3]_-28, 1907: **p 1906( 1905 / 1907 ) : 26: 4
2063: [5][7][5]_-21, 2063: **p 2062( 2061 / 2063 ) : 26: 4
2099: [8][13][8]_-17, 2099: **p 2098( 2097 / 2099 ) : 26: 4
2309: [1][573][1]_-577, 2309: **p 2308( 2307 / 2309 ) : 29: 4
2879: [4][15][4]_25, 2879: **p 2878( 2877 / 2879 ) : 32: 4
3023: [2][49][2]_-53, 3023: **p 3022( 3021 / 3023 ) : 32: 4
3167: [7][18][7]_20, 3167: **p 3166( 3165 / 3167 ) : 32: 4
4139: [3][38][3]_-44, 4139: **p 4138( 4137 / 4139 ) : 33: 4
5099: [3][43][3]_-49, 5099: **p 5098( 5097 / 5099 ) : 36: 4
6599: [7][18][7]_-32, 6599: **p 6598( 6597 / 6599 ) : 36: 4
6719: [3][8][3]_46, 6719: **p 6718( 6717 / 6719 ) : 36: 4
7643: [5][11][5]_38, 7643: **p 7642( 7641 / 7643 ) : 38: 4
8423: [8][9][8]_-33, 8423: **p 8422( 8421 / 8423 ) : 38: 4
9743: [8][31][8]_33, 9743: **p 9742( 9741 / 9743 ) : 41: 4
10079: [5][11][5]_-46, 10079: **p 10078( 10077 / 10079 ) : 41: 4
11423: [2][21][2]_-81, 11423: **p 11422( 11421 / 11423 ) : 45: 4
13103: [23][7][23]_-24, 13103: **p 13102( 13101 / 13103 ) : 46: 4
15383: [11][31][11]_36, 15383: **p 15382( 15381 / 15383 ) : 46: 4
16139: [2][35][2]_-99, 16139: **p 16138( 16137 / 16139 ) : 47: 4
16487: [2][53][2]_-105, 16487: **p 16486( 16485 / 16487 ) : 47: 4
17027: [3][4][3]_-76, 17027: **p 17026( 17025 / 17027 ) : 47: 4

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreFundamental080706
Aug_07_2006

On further reflection, [2][2] must be considered to be "non-trivial" to
generate just primes in the aforementioned list. Otherwise, numbers like
38 show up. 38's factors are two and 19. The base_2 representation for
38 suffers from a wrap-around effect since there aren't enough binary
digits to express it as [19][19]. Therefore, it's not a palindrome in
base 2. Just in base 19. If we treat [2][2] as trivial, then [2][1][2]_4
will show up as the sole non-trivial palindrome. Since it has 3 digits,
it'll show up in this list. On the other hand, if [2][2] is non-trivial,
then 38 has 2 non-trivial palindromes, which excludes it from the list.

So like it or not, I think we're back to considering the odd number
palindrome {[1][((N-1)/2)-2][1]_-((N-1)/2)} as trivial, but the even
palindrome {[2][2]} as non-trivial. This choice appears to give 2
mechanisms for generating lists of primes (0 non-trivial palindromes and 1
non-trivial palindrome). Considering [2][2] as trivial appears to make
both lists contain primes and evens. (As discussed before, I'm sure about
primacy of odds for the 0 non-trivial list. Not sure about the 1
non-trivial list yet.)


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwoTwo080706
Aug_07_2006

Looking over all representations, it looks like 5 should also be included
in last night's list. Dunno, but I guess it was filtered out in the other
list because I was looking at bases up through sqrt(N). No time to figure
it out now.

bash-3.1$ ./oneplus | egrep ': 4$' | egrep -v '^[0-9]*: [0-9]|^[0-9]*[02468]:'
5: [1][0][1]_2, 5: **p 4( 3 / 5 ) : 4: 4
9: [1][0][0][1]_2, 9: **c 8( 7 / 9 ) : 5: 4
11: [1][1][1][1][1]_-2, 11: **p 10( 9 / 11 ) : 5: 4
19: [1][3][1]_-6, 19: **p 18( 17 / 19 ) : 8: 4
59: [3][2][3]_4, 59: **p 58( 57 / 59 ) : 9: 4
83: [3][1][3]_5, 83: **p 82( 81 / 83 ) : 11: 4
149: [1][33][1]_-37, 149: **p 148( 147 / 149 ) : 14: 4
263: [3][4][3]_-10, 263: **p 262( 261 / 263 ) : 14: 4
359: [2][13][2]_-17, 359: **p 358( 357 / 359 ) : 18: 4
467: [2][1][2]_15, 467: **p 466( 465 / 467 ) : 18: 4
503: [7][6][7]_8, 503: **p 502( 501 / 503 ) : 18: 4
983: [3][11][3]_-20, 983: **p 982( 981 / 983 ) : 21: 4

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MinPlusOne080706
Aug_06_2006

Here are the palindromic forms for all numbers up to 71610 with 1
palindrome more than the trivial ones... Interesting that (4,4),(6,6),
(8,8), (9,9), and (10,10), etc... are all absent. It makes sense since
composite pairs can't have just 1 non-trivial palindrome because they also
have pairs of factors. i.e. anything with (8,8) will also have (4,4) and
(2,2). Likewise (6,6) implies (3,3) and (2,2). Therefore, they can't
have trivials + 1 palindromic represenations.

This list came from the pal/non-pal data, not the more comprehensive data
which counted "trivial" palindromes too. So I suppose [2,2] should
actually be removed from the list.

As an example, [2][93][2] appears in this list. A look at the data
reveals that it comes from 46199. [2][93][2]_-177. Windows calculator
verifies that 2(177^2) - 93(177) + 2 = 46199.

An example with 2 numbers is (11,11), which maps to 2123 (base 192) and
17567 (base 1596).

1 [101][101]
2 [11][11]
3 [11][24][11]
4 [11][31][11]
5 [11][47][11]
6 [11][50][11]
7 [13][13]
8 [19][19]
9 [19][30][19] ... (49019)
10 [19][3][19]
11 [1][0][0][1]
12 [1][17733][1]
13 [1][1][1][1][1]
14 [1][33][1]
15 [1][3][1]
16 [1][573][1]
17 [1][7569][1]
18 [23][20][23]
19 [23][28][23]
20 [23][7][23]
21 [2][13][2]
22 [2][1][2]
23 [2][21][2]
24 [2][2]
25 [2][35][2]
26 [2][49][2]
27 [2][53][2]
28 [2][71][2]
29 [2][85][2]
30 [2][93][2]
31 [34][33][34]
32 [35][17][35]
33 [37][37]
34 [39][5][39]
35 [3][11][3]
36 [3][148][3]
37 [3][16][3]
38 [3][17][3]
39 [3][1][3]
40 [3][2][3]
41 [3][38][3]
42 [3][3]
43 [3][43][3]
44 [3][49][3]
45 [3][4][3]
46 [3][55][3]
47 [3][61][3]
48 [3][76][3]
49 [3][89][3]
50 [3][8][3]
51 [43][43]
52 [4][15][4]
53 [5][11][5]
54 [5][41][5]
55 [5][5]
56 [5][67][5]
57 [5][7][5]
58 [79][79]
59 [7][15][7]
60 [7][18][7]
61 [7][6][7]
62 [7][75][7]
63 [7][7]
64 [83][83]
65 [89][89]
66 [8][13][8]
67 [8][25][8]
68 [8][31][8]
69 [8][37][8]
70 [8][53][8]
71 [8][9][8]
72 [9][7][9]

And this leads to a list that looks like a pleasant surprise... a way to
create a list of primes (after 9)...

bash-3.1$ egrep ': 1$' AllPals071906b.txt | egrep -v '\[[0-9]*\]\[[0-9]*\]_' | awk -F: '{printf "%s, ", $1}'

9, 11, 19, 59, 83, 149, 263, 359, 467, 503, 983, 1439, 1907, 2063, 2099,
2309, 2879, 3023, 3167, 4139, 5099, 6599, 6719, 7643, 8423, 9743, 10079,
11423, 13103, 15383, 16139, 16487, 17027, 19379, 20123, 20627, 23099,
25583, 30293, 33623, 33647, 37547, 40127, 46199, 49019, 49499, 55103,
55787, 59447, 59747, 62507, 62639, 63299, 64019, 64319, 65063, 65543,
68507, 69767, 70139, 70583, 70949

Numbers with exactly 1 non-trivial palindromic representation where the
palindrome is 3 digits or more. I think I checked them all. Except for
9, they're all prime. If 9 can be explained as a special case, this might
be a better list than the minimal pals, since it's not interspersed with
even numbers.

Not found at AT&T. With or without the troublesome 9 (1001_2).

Still not an easy list for me to generate. Very expensive, in fact.

So how do I say my guess succinctly? Let's see.

Given the trivial palindromes, from here:
http://taz.cs.wcupa.edu/~spalmer/PrimeSumm.txt

Doesn't matter if we include [2][2]_((N-2)/2) or not, since they're
excluded by the where clause.

Any number which can be represented by exactly 1 non-trivial palindrome,
where that palindrome is 3 digits or more, will be a prime number.

I think that says what I mean.

Tying the two sections of this posting together. I look at the example of
[7][75][7] in the data where it is the only palindrome representation of a
number. The number is 62507 (base -100). I check it for primacy and find
that it is a prime, as expected.

It should be noted that I'm not saying anything at all about [7][75][7]
when there are other non-trivial palindromic representations for the same
number. i.e. 70307 has 8 palindromes, 1 is [7][75][7]_95 and it's a
composite. 70709 has 6 palindromes, 1 is [7][75][7]_-106. It's a prime.
Neither of these numbers are relevant to the lists above.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#OnePlusMin080606
Aug_05_2006

53271 / 53322 :- prime palindromes / prime "non-palindromes" at 656707.
99.904%.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PalPCT080506
Aug_04_2006

Here are a couple more sequences I hadn't thought of before. No value to
them at all that I can think of...

Numbers that are palindromes in 2 consecutive positive bases...
10, 46, 67, 92, 98, 104, 130, 135, 154, 178, 185, 227, 235, 292, 300, 373

For example, 292 is (5,6,5)_7 and (4,4,4)_8 [and (4,4,4)_-9 for whatever
that's worth].

Numbers that are palindromes in 3 consecutive positive bases...
178, 300, 373, 676, 1111, 1702, 2473, 3448

For example, 300 = (6,0,6)_7, (4,5,4)_8 and (3,6,3)_9 [and (3,6,3)_-11].

Both sequences need to be double-checked. I only did a cursory check.
So far I haven't found any palindromes in 4 or more consecutive bases
and haven't checked the negative bases at all.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Consecs080406
Aug_02_2006

Someone else used the word palindromic, so I guess it's a real word...
http://www.worldofnumbers.com/palprim3.htm

Also. I just noticed, it looks like the first twin palindrome in a base
pair is always 101. BASE^2 + 1. ie. 4^2+1 is 17, so we know 17 is a twin
palindrome in base 4. Obviously, this palindrome might be prime or
composite. (composite example, 26)

17: [1][0][0][0][1]_2, [1][0][0][0][1]_-2, [2][1][2]_-3, [1][0][1]_4, [1][0][1]_-4, **7( 11 / 17 ) : 5
26: [2][2][2]_3, [2][2][2]_-4, [1][0][1]_5, [1][0][1]_-5, [2][2]_12, **12( 20 / 26 ) : 5


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Palindromic080206
Aug_02_2006

Found a bigger non-identical twin. Looks like base +/- 2 have a
propensity for these non-identical twin palindrome primes. 524287 is a
repunit in base 2, but it's 11 followed by lots of 0's followed by 11 in
base -2.

524287:
[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1]_2,
[1][1][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][1][1]_-2,

It's amazing to me too that I'm up to 605509 and 173 is still the
only twin palindrome prime found in bases +/- 3. I think I already
mentioned that it's an identical twin (2,0,1,0,2).
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FratTwinPal080206
Aug_02_2006

Found 589681 overnight. A prime with 115 palindromic representations.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AnotherPal080206
Aug_01_2006

Forgot another question which I'd really like to look at eventually.
What does a map of the palindromes look like? I'm thinking of running the
number along one axis and the positive and negative bases along the other.
I'm also thinking to differentiate among repunits, palindromes and all
other numbers. Distinct symbols will be in the legend for

prime repunits
composite repunits
prime palindromes
composite palindromes
prime asymmetric numerals
composite asyms

Another type of numeral is that with repeating sequences, but I'm going to
continue ignoring that, since I've already bitten off more than enough for
quite a while. For example, 43214321, is not a palindrome, but it is
somewhat symmetric. On the other hand, it can never be prime, by basically
the same reasoning as why the repunits with composite numbers of digits
couldn't be prime so it's probably not very interesting.

Battery's dying. Child's sleeping. Gotta go.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NudderQuestion080106
Aug_01_2006

Ugh. Just looked for twin palindromes in the prime+composite data from
the other day. Doesn't it figure that since I stopped ignoring the
"trivial" palindromes, every number's a twin palindrome now too. All are
palindromes in base +/- (N-1).

(Incidentally, I did kill that program around 670M instead of letting it
run 'til the next morning to see if it would crash my laptop.)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwinPals080106
Aug_01_2006

I forgot to mention. I did check AT&T, the other day, for the sequence of
minimal palindromes referenced here...
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ThreePals073006

They didn't seem to have it. I guess maybe it's not of general interest.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FollowUp080106
Aug_01_2006

Still no new numbers with 113 or more palindromic representations. Found
526681 with 108 and 540541 with 107. I'm not sure, but I think I had
already mentioned 514081 with 106. The highest twin palindrome prime so
far is 560213... (2,0,1,0,2) in base +/- 23. I guess 8191 is still the
highest non-identical palindrome prime found, but I haven't written a
program to check for certain, so that might be wrong. The prime
palindrome ratio so far is 47690 / 47738; 99.899% of primes are
(non-minimal) palindromes up through 581981. As I recall, the prime +
composite number was already higher than that when I killed it a week or
so back.

Probably nothing useful can come from continuing to generate prime number
data at this point, but it's been running so long I don't have the heart
to kill it. I think I'm getting close to the point where there's no way
around having to think if I'm to move any closer to wherever I'm going.
I think it might still be useful to look at more data on primes +
composites before resorting to thinking though.

For future review... What are some questions?

1.) First and foremost, is there an 'easy' way to generate the minimal
palindrome list. If so, it'll be easy to find big primes, since all
minimal palindromes are prime, (ending in 3, 7 or 9 in base 10), or else
even. It's definitely easy to tell whether an even is prime or not. :-)

2.) Why are identical twins so much more common than non-identical twins
(and is that true for composites as well as primes)? Is the list of
non-identical twin palindromes infinite? Same for identical twin primes?

3.) Are there characteristic differences between primes and composites?
For example, does a high or low palindrome count make a number more or
less likely to be prime?

4.) Is there an efficient way to determine the number of palindromic
representations that exist for a number?

5.) Is the list of minimal palindromes infinite? (As is apparent from
question 1, I'm assuming this one is yes) If not, what's the biggest
minimal palindrome.

As mentioned previously, a minimal palindrome is a number with only 3
palindromic representations in bases from +/- 2 through +/- (N-1).

I suppose I could probably save myself some time by just posting to a math
news group. I'm sure this stuff has been looked over, but I'm having fun
and I'm not in any hurry.

Winnie the Pooh's just about over, so I've got a 4 year-old to put to bed.
That's it for now.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeUpdate080106
Jul_30_2006

Here are the "minimal palindromes" so far...

Sun Jul 30 21:59:45 EDT 2006
1 0 0
2 0 0
3 2 2
4 2 2
6 4 2
8 5 3
12 5 3
1019 21 3
1754 26 3
1994 26 3
4679 33 3
4919 33 3
5387 36 3

So the numbers with three palindromic representations are either prime or
even. Up to 6, I'm willing to just throw out as special cases, since
there aren't enough digits in the number systems from 2 through 5 to
accomodate the trends observed in the higher numbers.

I'm getting near this machine's capacity on the primes + composites.
I've already generated 560M of data and I'm done through 5705. Have to
modify that program to count the palindromes without printing any
representations and run that on my other computer. I guess I'll let this
one run, then kill it in the morning. It'll be somewhere around 2G by
then I guess. I wonder what windows + cygwin is gonna do with a 2G file.
Maybe I'd better kill it tonight.

For any of this to be of any use, there's got to be a way to get a handle
onto these numbers without looking at every representation of every
number. So I've got to start thinking about what it is that I'm looking
at.

I want a list of numbers with no palindromic representations other than
(1,1)_(N-1); (1,N-1,1)_-(N-1); and

one of [(2,2)_(N-2)/2 or (1,((N-1)/2)-2,1)_((N-1)/2)] depending upon
whether it's even or odd.

(and N_[N+1 and higher] which I'm still ignoring.)

Said another way, if I graph equations for all possible palindromes, I'm
looking for the nodes where only 3 equations intersect. When I find those
vertices, they'll be even or prime.

My computer chokes if I launch a web browser right now, so I can't check
AT&T for the sequence: 1019, 1754, 1994, 4679, 4919, 5387. I'll look for
that tomorrow I guess. (with and without the leading 8, 12. I think
they're part of the sequence, but if someone found a different sequence
containing the same numbers, 8 and 12 might be left out.)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ThreePals073006
Jul_30_2006

OK. I think I'm gonna have to start over. The necessary computing will
be painfully expensive though. All numbers can be represented as
palindromes. I should stop throwing out trivial palindromes of any sort
and start looking numbers with minimum numbers of palindrome
representations. There are no non-palindromes. Stop talking about them.

To that end, I've started a new program saving all representations of all
integers. This is gonna get real slow and the data file's gonna get real
big real fast. We'll see how long my laptop can hold up. Probably not
very long. Up to a little over a thousand so far, here are the
minimums...

Sun Jul 30 17:10:46 EDT 2006
1 0 0
2 0 0
3 2 2
4 2 2
6 4 2
8 5 3
12 5 3
1019 21 3

The second column is the maximum palindrome count for any number so far.
The 3rd column is the number of palindromes for the number in the first
column.

I'm checking bases 2 through N-1. That's why 0's in 1 and 2. No bases
checked. I don't see any value to checking base 1 or base N and on.

I think I'm not gonna see any more with less than 3, since we know there
are 2 trivials for every number and at least one trivial each for evens
and odds. Seems that the minimum after 6 should be 3. I'm guessing we'll
see 3's everywhere I had 0's before, but I haven't really thought that
through. If so, it's a very time-consuming way of generating a list of
primes, but it will be a list of primes. Next candidate is 4679. It'll
probably be some time before I get there, so I'll check back later.

Meanwhile, on the prime palindrome front, still nothing new with more than
113. I have found 526681 with 108 (+ 2 or 3 trivials). Largest twin
prime palindrome so far is 530393... (5,0,17,0,5) in base +/- 18.

Uh oh. 1754 just popped up with a 3 count. So consistent treatment of
the "trivial" palindromes brings some even, non-primes, into the list.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MinPals073006
Jul_28_2006

Found 498961 overnight with 113 non-trivial palindromic representations.
Also, 514081 with 106. No other new ones with 100 or more. I'm up to
515311 in checking primes.

New twin palindrome primes:
500009 - (13,0,3,0,13) in base +/- 14
501577 - (13,0,11,0,13) in base +/- 14
504311 - (6,0,11,0,6) in base +/- 14

All identical.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#OneThirteen072806
Jul_27_2006

Still haven't found any more numbers with 108 or more palindromes. We did
find 478801 today with 102 palindromes and 471241 with 106.

No new non-palindromes either. Guess I won't have any of them until I get
around to fixing the prime+composite program. The prime program is
retreading old ground in that respect.

For whatever it's worth (probably nothing), I noticed today that the
binary representations for every non-palindrome I checked had an odd
numbers of zeros in it.

If there's a way to construct those numbers, it's not jumping out at me
though. I'm doubtful that there is.

Oh. The new highest twin palindrome prime to date is 487603, (3,0,19,0,3)
in bases +/- 20. Non-identical twin palindromes seem to be somewhat rare.
In fact, I could've overlooked some, but I think 8191 is still the highest
one (base +/- 2) I've found.

Also, it looks like 111_b, where b is positive is also always 111_-(b+1).
For example, 43 = 111_6 and 111_-7, so 7^2 - 7 should equal 6^2 + 6, and
it does. So x^2 + x + (x+1) seems to be (x+1)^2. That's pretty cool.

FOIL verifies the observation.
(x+1) * (x+1) = x2 + x + x + 1


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimePalsUpdt072706
Jul_26_2006

I'll have to put in negative bases later. Here's a javascript program
that'll display lists of digits in the browser for positive bases. It's
pretty painful for big numbers. On my machine, mozilla is less painful
than maxthon (MS/IE). YMMV

http://mercury.ccil.org/~remlaps/javascript/Reps.html

Just enter an integer, N, and it will spit back every representation from
base 2 through N/2.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#RepLists072606
Jul_26_2006

Aha. I did hit a limit. Here's my offending line of code...

for ( BASE=2; BASE<2000048 && BASE <= (lcv)/2; BASE++ )

Duh.

I wonder what I was thinking when I did that? Doesn't seem that the first
clause in the AND phrase has much purpose except to break my program when
I'm not expecting it. I must've had a reason for it somewhere along the
way though... Oh well. So I've gotten as far as I can in primes +
composites for now. I don't have a compiler on that machine, so
recompiling and resuming will take some time.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Wed_Jul_26_19:43:14_EDT_2006.11829
Jul_26_2006

No new numbers with 108 or more palindromes today. We did find 453601
with 106 palindromes. Nothing else over 100. The highest twin palindrome
prime is 459271, an identical twin in bases +/- 16 (7,0,2,0,7). It's also
a palindrome in base 2 (1110000001000000111_2, 19 digits.)

The biggest non-palindromes found so far are:
4069034: **2000047( 4068906 / 4069034 ) : 0
4113839: **2000047( 4113710 / 4113839 ) : 0

Uh oh. An even number? That's wrong. It's 22 in base 2034516. I only
checked up to 2000047. Looks like I'm not checking enough bases. Ugh.
The primes are alright, but these primes + composites might still have
some undetected palindromes. Guess I'll have to check every base up to
+/- [N-2], instead of trying to skip some to save procesing.

Hmm. These last 8 or so all stopped at base 2000047. I wonder if I hit
some sort of limit that I wasn't aware of. Maybe the numbers before those
are all OK. Dunno. We'll see.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CheckIn
Jul_26_2006

Actually, I just noticed, the algebra here...
http://mercury.ccil.org/~remlaps/weblog_2006/mathematics_index.html

Works for just about all the positive bases, it was only my assumption
that limited it to base 10. Looks like every number that ends in 1 in
any base is a palindrome in a negative base. I guess you just have to
be careful to represent k in the right base.

i.e. 82 = 10001_3 = k=1000_3 = 27, 27 - 10_3 = 27 - 3 = 24, so 82 is also
(1,24,1)_-27. Windows calculator says 27^2 - 24*27 + 1 = 82, so it works
out.

I would not have guessed this. As soon as I find that a number ends in 1
in some positive base, I know it's a negative base palindrome. So among
other things, I now know that the no-palindrome numbers I've found must
not end in 1 in any base of notation. Not just base 10. They cannot be
equal to kx + 1 for any positive integers k & x. I don't know what that
tells me. Probably nothing. It's intriguing though.

For whatever it's worth, this does tell me that the no-palindrome numbers
above 6 must all end in 5 in base 6, since it is known that all base 6
primes end in 1 or 5.

Checking that claim on 1019, one of the non-palindromes, I find 1019_10
goes to 4415_6 and the claim holds up.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOnePals072606
Jul_25_2006

Today we found 415801 with 108 palindrome representations. We also found
some new twin primes by checking past base +/- 36. In the stale
prime+composite set, the highest is 71500, which is an identical twin in
base +/- 57 (22,0,22). In the still growing prime set, the highest is
424939... an identical twin in bases +/- 14 (11,0,12,0,11).

Here are the top 10 non-palindromes... I hope they're all primes,
although primes + composites are being checked... If any are not prime,
then there's something wrong.

3409223: **1704611( 3409108 / 3409223 ) : 0
3430079: **1715039( 3429963 / 3430079 ) : 0
3452279: **1726139( 3452162 / 3452279 ) : 0
3541823: **1770911( 3541705 / 3541823 ) : 0
3569927: **1784963( 3569808 / 3569927 ) : 0
3623519: **1811759( 3623399 / 3623519 ) : 0
3662987: **1831493( 3662866 / 3662987 ) : 0
3672827: **1836413( 3672705 / 3672827 ) : 0
3720359: **1860179( 3720236 / 3720359 ) : 0
3766943: **1883471( 3766819 / 3766943 ) : 0
3810767: **1905383( 3810642 / 3810767 ) : 0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CheckIn072506
Jul_25_2006

I still haven't done the algebra, but it appears from scanning through the
data that one relationship that forces all base 10 numbers ending in 1 to
be palindromes is this...

10k + 1 (base 10) = [1][k-10][1] (base -k)
=k^2 - (k * (k-10)) + 1
=k^2 - (k^2 - 10k) + 1
=-(-10k) + 1
=10k + 1

OK. Now I've done the algebra :)

i.e. to make up a number...
171131_10 = [1][17103][1]_-17113

To check that...
17113^2 = 292854769
17103 * 17113 = 292683639
292854769 - 292683639 + 1 = 171131

So it checks out. Appparently all base 10 numbers that end in 1 are, in
fact, 3 digit palindromes in a negative base. Just forget about 1 and 11.
I think 1's a special case, since k would be 0. I don't feel like
thinking about it right now. 11 is a palindrome, but that doesn't show up
in my data because base -10 is considered 'trivial' for N=11.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOne072506
Jul_24_2006

Forgot to mention... The new biggest twin palindrome prime I've found is
355507, which is an identical twin in bases +/- 15 (7,0,5,0,7).

next biggest is 355057, Also +/- 15 (7,0,3,0,7)

(*
I hope. Haven't verified those representations.... Oh.... OK. Yep.
Windows calculator says
7(15)^4 + 5(15)^2 + 7 = 355507 and
7(15)^4 + 3(15)^2 + 7 = 355057.

The web says their both primes.

That's a pretty cool pair of numbers. Phew.
:-)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwinPrimeAdd072406
Jul_24_2006

So it looks like just about all base_10 numbers that end in 1 really are
(non-trivial) palindromes in at least 1 negative base.

$ egrep '^[0-9]*1:' AllPals071906b.txt | egrep -v ' \[1\]\[[0-9]*\]\[1\]_-'
1: **1( 0 / 1 ) : 0
11: [1][1][1][1][1]_-2, **4( 5 / 11 ) : 1

Apparently all except 1 and 11 can be represented in a negative base with
the form (1,x,1). I haven't worked it out algebraically yet, but I'm
willing to believe that it's true. That can be rephrased to say that if-

N = 10k + 1, then 10k is always x^2 - jx for some integers x and j.

i.e.
20 = 5^2 - 1(5), so 21 (20 + 1) is a palindrome (1,1,1) in base -5. (k=2,x=5,j=1)
20 = 10^2 - 8(10), so 21 is (1,8,1) in base -10. (k=2,x=10,j=8)
30 = 10^2 - 7(10), so 31 = (1,7,1) in base -10. (k=3,x=10,j=7)
120 = 12^2 - 2(12), so 121 = (1,2,1) in base -12 (k=12,x=12,j=2)

It's plausible to think I can find x & j to make this work out for any
integer = 10k+1 (k>=2). It also fits my observations so far, up to
71,607. If I get some time with a pen and paper, maybe I'll take a look
at the algebra. The proof does seem to be within reach.

It works for 11 too, (1,9,1)_-10, but that's one of the trivial
palindromes I've been ignoring, so it doesn't show up in my data.

Incidentally, 107 is still the most representations I've found for any
number (still at 332641). 393121 showed up with 106 now and 388081 with
101. I'm only running full checks on primes now. I killed the one doing
primes + composites. Not enough CPU.

Here are today's highest non-palindromes. These include primes and
composites, but as I mentioned before, they should all turn out to be
primes. In base 10, they should all end in 3,7 or 9 I now suppose too.
2636339: **1318169( 2636243 / 2636339 ) : 0
2652719: **1326359( 2652622 / 2652719 ) : 0

Note the ratio too. 2652622 palindromes out of 2652719 integers. 99.996%
palindromes (and seemingly growing towards 100% ... 99.993 or so at this
time yesterday). I'm still troubled by what to do about the 2 digit,
positive base palindromes. Good thing I'm not doing this for a grade or a
salary. :-)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrailOnePals072406
Jul_23_2006

Non-palindromes down to 757,343... Interesting that so far none of them
end in '1' (except 1). (11 excluded from palindromes, along with the other
'trivial' palindromes... other 2 digit palindromes are included
[2,2],[3,3], etc...).

C:\Documents and Settings\Papa\primes>fastpal | find /i ": 0"
1: **1( 0 / 1 ) : 0
2: **1( 0 / 2 ) : 0
3: **1( 0 / 3 ) : 0
4: **2( 0 / 4 ) : 0
6: **3( 1 / 6 ) : 0
1019: **509( 1013 / 1019 ) : 0
4679: **2339( 4672 / 4679 ) : 0
4919: **2459( 4911 / 4919 ) : 0
5387: **2693( 5378 / 5387 ) : 0
8147: **4073( 8137 / 8147 ) : 0
12539: **6269( 12528 / 12539 ) : 0
27299: **13649( 27287 / 27299 ) : 0
29663: **14831( 29650 / 29663 ) : 0
46679: **23339( 46665 / 46679 ) : 0
54959: **27479( 54944 / 54959 ) : 0
58679: **29339( 58663 / 58679 ) : 0
73859: **36929( 73842 / 73859 ) : 0
74759: **37379( 74741 / 74759 ) : 0
93047: **46523( 93028 / 93047 ) : 0
111263: **55631( 111243 / 111263 ) : 0
113327: **56663( 113306 / 113327 ) : 0
133919: **66959( 133897 / 133919 ) : 0
142907: **71453( 142884 / 142907 ) : 0
152519: **76259( 152495 / 152519 ) : 0
152567: **76283( 152542 / 152567 ) : 0
169019: **84509( 168993 / 169019 ) : 0
197339: **98669( 197312 / 197339 ) : 0
246899: **123449( 246871 / 246899 ) : 0
260399: **130199( 260370 / 260399 ) : 0
279479: **139739( 279449 / 279479 ) : 0
294167: **147083( 294136 / 294167 ) : 0
306899: **153449( 306867 / 306899 ) : 0
319259: **159629( 319226 / 319259 ) : 0
344363: **172181( 344329 / 344363 ) : 0
350423: **175211( 350388 / 350423 ) : 0
352043: **176021( 352007 / 352043 ) : 0
370247: **185123( 370210 / 370247 ) : 0
371699: **185849( 371661 / 371699 ) : 0
373343: **186671( 373304 / 373343 ) : 0
388187: **194093( 388147 / 388187 ) : 0
390959: **195479( 390918 / 390959 ) : 0
402947: **201473( 402905 / 402947 ) : 0
408719: **204359( 408676 / 408719 ) : 0
428567: **214283( 428523 / 428567 ) : 0
429119: **214559( 429074 / 429119 ) : 0
493463: **246731( 493417 / 493463 ) : 0
494783: **247391( 494736 / 494783 ) : 0
527447: **263723( 527399 / 527447 ) : 0
536399: **268199( 536350 / 536399 ) : 0
541799: **270899( 541749 / 541799 ) : 0
582887: **291443( 582836 / 582887 ) : 0
606863: **303431( 606811 / 606863 ) : 0
632447: **316223( 632394 / 632447 ) : 0
753587: **376793( 753533 / 753587 ) : 0
757343: **378671( 757288 / 757343 ) : 0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Nonpals072306
Jul_23_2006

Big jump from 90 to 107 palindromes. 287281 has 90, 332641 has 107.
Thus far, there are none with 91 through 106. I'm sure they'll get filled
in though, if I wait long enough.

The biggest non-palindrome so far is 319259.

The biggest twin-palindrome so far is 341569, which is an identical twin
in bases +/- 24 (1,0,17,0,1).

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ChkPt072306
Jul_21_2006

Here are the non-palindromes up to 1 million, after searching primes and
composites. (left most column)

1: **1( 0 / 1 ) : 0
2: **1( 0 / 2 ) : 0
3: **1( 0 / 3 ) : 0
4: **2( 0 / 4 ) : 0
6: **3( 1 / 6 ) : 0
1019: **509( 1013 / 1019 ) : 0
4679: **2339( 4672 / 4679 ) : 0
4919: **2459( 4911 / 4919 ) : 0
5387: **2693( 5378 / 5387 ) : 0
8147: **4073( 8137 / 8147 ) : 0
12539: **6269( 12528 / 12539 ) : 0
27299: **13649( 27287 / 27299 ) : 0
29663: **14831( 29650 / 29663 ) : 0
46679: **23339( 46665 / 46679 ) : 0
54959: **27479( 54944 / 54959 ) : 0
58679: **29339( 58663 / 58679 ) : 0
73859: **36929( 73842 / 73859 ) : 0
74759: **37379( 74741 / 74759 ) : 0
93047: **46523( 93028 / 93047 ) : 0
111263: **55631( 111243 / 111263 ) : 0
113327: **56663( 113306 / 113327 ) : 0
133919: **66959( 133897 / 133919 ) : 0
142907: **71453( 142884 / 142907 ) : 0
152519: **76259( 152495 / 152519 ) : 0
152567: **76283( 152542 / 152567 ) : 0
169019: **84509( 9019 / 9020 ) : 0
197339: **98669( 37338 / 37340 ) : 0
246899: **123449( 86897 / 86900 ) : 0
260399: **130199( 100396 / 100400 ) : 0
279479: **139739( 119475 / 119480 ) : 0
294167: **147083( 134162 / 134168 ) : 0
306899: **153449( 146893 / 146900 ) : 0
319259: **159629( 159252 / 159260 ) : 0
344363: **172181( 184355 / 184364 ) : 0
350423: **175211( 190414 / 190424 ) : 0
352043: **176021( 192033 / 192044 ) : 0
370247: **185123( 210236 / 210248 ) : 0
371699: **185849( 211687 / 211700 ) : 0
373343: **186671( 213330 / 213344 ) : 0
388187: **194093( 228173 / 228188 ) : 0
390959: **195479( 230944 / 230960 ) : 0
402947: **201473( 242931 / 242948 ) : 0
408719: **204359( 248702 / 248720 ) : 0
428567: **214283( 268549 / 268568 ) : 0
429119: **214559( 269100 / 269120 ) : 0
493463: **246731( 333443 / 333464 ) : 0
494783: **247391( 334762 / 334784 ) : 0
527447: **263723( 367425 / 367448 ) : 0
536399: **268199( 376376 / 376400 ) : 0
541799: **270899( 381775 / 381800 ) : 0
582887: **291443( 422862 / 422888 ) : 0
606863: **303431( 446837 / 446864 ) : 0
632447: **316223( 472420 / 472448 ) : 0
753587: **376793( 593559 / 593588 ) : 0
757343: **378671( 597314 / 597344 ) : 0
838919: **419459( 678889 / 678920 ) : 0
850247: **425123( 690216 / 690248 ) : 0
858239: **429119( 698207 / 698240 ) : 0
888263: **444131( 728230 / 728264 ) : 0
901679: **450839( 741645 / 741680 ) : 0
935399: **467699( 775364 / 775400 ) : 0
901679: **450839( 741645 / 741680 ) : 0
935399: **467699( 775364 / 775400 ) : 0
957263: **478631( 797227 / 797264 ) : 0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NonPals072106
Jul_20_2006

Today, my laptop found 196561, with 87 palindromic representations.
197339 appears to be the highest non-palindrome prime so far ....

Wow! That's quite a gap too. The next highest non-palindrome was 169019.
Somewhere around 2351 palindrome primes between the two non-palindromes.

I'm puzzled by what to do when I start looking at composites. The problem
is the 2 digit palindromes.

22 - Multiples of 2 in every base (above 2)
33 - Multiples of 3 in every base (above 3)
44 - Multiples of 4 in every base (above 4)
...
...

The question is whether to treat them as trivial and ignore them or to
count them as palindromes.

I'm inclined to count them, but that's not really consistent with throwing
out the all odd number palindromes from the negative bases,
([1][((n-1)/2)-2][1]). I stripped those. If I put the odd palindromes
back in, though, then every number is a palindrome again. That's
unpleasant. On the other hand, if I leave the odds out, and the 2 digit
positive base palindromes in, there are still non-palindromes ([over 6]
they're all prime, since they're not multiples of anything).

I'm thinking that for now I'll leave 'em in. I can always strip 'em out
again later. I'm not liking either of the options though.

Oh. I found this paper tonight too...
http://arxiv.org/PS_cache/math/pdf/0405/0405056.pdf

Someone (actually a few someones) smarter than me is looking at primes and
palindromes. It's got two dates, one in 2004 and July 15, 2006 in another
place. I sure wish I could understand what it says. I don't think
they're looking at negative bases or collections of bases though. Just
one positive base at a time.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Pals072006
Jul_19_2006

This one's too big for CCIL. Here's a summary report based on the primes
from 2 through somewhere around 150,000 and bases +/-2 through +/-36.

http://taz.cs.wcupa.edu/~spalmer/PrimeSumm.txt

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeSummary071906
Jul_19_2006

Prime and composite palindromes in base +/- 2
7, 17, 21, 31, 51, 65, 85, 127, 195, 257, 273, 325, 341, 455, 511, 771,
819, 1025, 1105, 1285, 1365, 1799, 2047, 3075, 4097, 4161, 4369, 4433,
5125, 5189, 5397, 5461, 7175...

Prime and composite palindromes in base +/- 10
101, 202, 303, 404, 505, 606, 707, 808, 909, 1111...

(1111_-10 = 19291. Obviously the rest match.)

The base 10 series matches 10 consecutive terms in the middle of this
one...
http://www.research.att.com/~njas/sequences/A109872
- "Palindromes such that successive difference of terms is also a
palindrome"

Yesterday's +/- base lists were just primes, no composites, although I
forgot to explicitly say so. This entry includes both primes and
composites.

Here are primes + composites with no non-trivial palindromic
representations...

1: **1( 0 / 1 ) : 0
2: **1( 0 / 2 ) : 0
3: **1( 0 / 3 ) : 0
4: **1( 0 / 4 ) : 0
5: **1( 0 / 5 ) : 0
6: **1( 0 / 6 ) : 0
1019: **508( 1010 / 1019 ) : 0
4679: **2338( 4667 / 4679 ) : 0
4919: **2458( 4906 / 4919 ) : 0
5387: **2692( 5373 / 5387 ) : 0

None of these series appear as listed here in the Online Encyclopedia of
Integer Sequences.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AllPals071906
Jul_18_2006

Palindromes in base 2 & -2...
7, 17, 31, 127, 257, 5189, 8191, 65537

Not in AT&T



Palindromes in base 3 & -3...
173




Palindromes in base +/- 4
17, 257, 787, 65537, 74017

Not in AT&T



Palindromes in base +/- 5
701, 1277, 1327, 2579

Not in AT&T



Palindromes in base +/- 6
37 1297 6521
Not in AT&T

Palindromes in base +/- 7
2549, 2647, 4951, 7451, 12157, 14461, 14657,
Not in AT&T

....

Palindromes in base +/- 10
101,
10301, 10501, 10601,
30103, 30203, 30403, 30703, 30803,
70207, 70507, 70607




Let's look at 173_3 and 173_-3 for a spot-check...
PrimePals071806.txt:173: [2][0][1][0][2]_3, [2][0][1][0][2]_-3,
[5][2][5]_-6, [2][1][2]_9, [1][39][1]_-43, **85( 37 / 40 ) : 5

2(3^4) + 1(3^2) + 2 = 162 + 9 + 2 = 173
2(-3^4) + 1(-3^2) + 2 = 162 + 9 + 2 = 173

That's handy. Not only are they both palindromes, but they're both the
same palindrome. I wonder if that's always the case. I guess 17's a good
one to check next...

17: [1][0][0][0][1]_2, [1][0][0][0][1]_-2, [2][1][2]_-3, [1][0][1]_4,
[1][0][1]_-4, **7( 4 / 7 ) : 5

Yep. +/-2 and +/-4 both match....

Aha... 31. +/- 2 differ, but both are palindromes...
31: [1][1][1][1][1]_2, [1][1][0][0][0][1][1]_-2, [1][2][1][2][1]_-3,
[1][1][1]_5, [1][1][1]_-6, [1][7][1]_-10, **14( 8 / 11 ) : 6

Let's spot check that one...
11111_2 = 16 + 8 + 4 + 2 + 1 = 31 - Check.
1100011_-2 = 64 - 32 - 2 + 1 = 31 - Check.

Phew...

Clearly the +/- 10 palindromes are all the same, since they have zero's in
what would be the negative places in base -10.

Someone really oughta write this stuff up carefully and get it into AT&T.
Someday maybe...
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PosNegBinPals071806
Jul_18_2006

2: **1( 0 / 1 ) : 0
3: **1( 0 / 2 ) : 0
5: **1( 0 / 3 ) : 0
1019: **508( 167 / 171 ) : 0
4679: **2338( 628 / 633 ) : 0
4919: **2458( 651 / 657 ) : 0
5387: **2692( 703 / 710 ) : 0
8147: **4072( 1015 / 1023 ) : 0
12539: **6268( 1488 / 1497 ) : 0
27299: **13648( 2979 / 2989 ) : 0
29663: **14830( 3207 / 3218 ) : 0
46679: **23338( 4811 / 4823 ) : 0
54959: **27478( 5574 / 5587 ) : 0
58679: **29338( 5922 / 5936 ) : 0

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MoreNonPals071806
Jul_18_2006

Positive and negative base (non-trivial palindrome) repunits

$ egrep ' \[1\](\[1\])*_' PrimePals071806.txt | awk -F: '{print $1" "}' | fmt

7 11 13 31 43 61 73 127 157 211 241 307 421 463 521 547 601 683 757 1093
1123 1483 1723 2551 2731 2801 2971 3307 3541 3907 4423 4831 5113 5701
6007 6163 6481 8011 8191 9091 9901 10303 11131 12211 12433 13421 13807
14281 17293 19141 19183 19531 20023 20593 21757 22621 22651 23563 24181
26083 26407 27061 ...

Apparently not in AT&T's encyclopedia...

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AllRepunits071806
Jul_18_2006

Negative base repunit primes (non-trivial palindromes)...

11 13 31 43 61 73 157 211 241 307 421 463 521 547 601 683 757 1123
1483 1723 2551 2731 2971 3307 3541 3907 4423 4831 5113 5701 6007 6163
6481 8011 8191 9091 9901 10303

Apparently identical to this one...
http://www.research.att.com/~njas/sequences/A059055 (Primes which can be
written as (b^k+1)/(b+1) for positive integers b and k.)

... but with 3 & 7 missing from the beginning. 3 & 7 are also negative
base repunit primes (111_-2 & 111_-3), respectively, but the repunits are
in the trivial palindromes, so they weren't found or listed.

It's not immediately obvious to me why these lists are basically the same
thing.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NegRepUnits071806
Jul_18_2006

That's alot of palindromes...

100801: [29][3][29]_-59, [8][105][8]_-119, [3][107][3]_-202,
[1][223][1]_225, [1][180][1]_240, [1][148][1]_252, [1][80][1]_280,
[1][62][1]_288, [1][36][1]_300, [1][5][1]_315, [1][5][1]_-320,
[1][36][1]_-336, [1][62][1]_-350, [1][80][1]_-360, [1][148][1]_-400,
[1][180][1]_-420, [1][223][1]_-448, [1][226][1]_-450, [1][270][1]_-480,
[1][304][1]_-504, [1][333][1]_-525, [1][380][1]_-560, [1][401][1]_-576,
[1][432][1]_-600, [1][470][1]_-630, [1][522][1]_-672, [1][556][1]_-700,
[1][580][1]_-720, [1][674][1]_-800, [1][720][1]_-840, [1][788][1]_-900,
[1][855][1]_-960, [1][908][1]_-1008, [1][954][1]_-1050,
[1][1030][1]_-1120, [1][1116][1]_-1200, [1][1180][1]_-1260,
[1][1269][1]_-1344, [1][1328][1]_-1400, [1][1370][1]_-1440,
[1][1511][1]_-1575, [1][1537][1]_-1600, [1][1620][1]_-1680,
[1][1744][1]_-1800, [1][1966][1]_-2016, [1][2052][1]_-2100,
[1][2195][1]_-2240, [1][2358][1]_-2400, [1][2480][1]_-2520,
[1][2764][1]_-2800, [1][2845][1]_-2880, [1][3118][1]_-3150,
[1][3330][1]_-3360, [1][3572][1]_-3600, [1][4007][1]_-4032,
[1][4176][1]_-4200, [1][4779][1]_-4800, [1][5020][1]_-5040,
[1][5582][1]_-5600, [1][6284][1]_-6300, [1][6705][1]_-6720,
[1][7186][1]_-7200, [1][8388][1]_-8400, [1][10070][1]_-10080,
[1][11191][1]_-11200, [1][12592][1]_-12600, [1][14393][1]_-14400,
[1][16794][1]_-16800, [1][20155][1]_-20160, [1][25196][1]_-25200,
[1][33597][1]_-33600, **50399( 66 / 66 ) : 71

Ends with 1 again.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SeventyOnePals071806
Jul_18_2006

So if we eliminate the known trivial palindromes and check bases just from
+/- 2 to +/- [((N-1)/2) - 1], I think this is the start of a sequence of
prime numbers with no palindromic representations...

2: **1( 0 / 1 ) : 0
3: **1( 0 / 2 ) : 0
5: **1( 0 / 3 ) : 0
1019: **508( 167 / 171 ) : 0
4679: **2338( 628 / 633 ) : 0
4919: **2458( 651 / 657 ) : 0
5387: **2692( 703 / 710 ) : 0
8147: **4072( 1015 / 1023 ) : 0
12539: **6268( 1488 / 1497 ) : 0

Very sparse, 99.4% palindromes up to 12539, but I'll bet it's still an
infinite list of non-palindromes.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NoPalsPosNeg071806
Jul_18_2006

So simple algebra tells me that a positive number, N, in base -(N-1) will
always be a 3 digit palindrome.

Call N-1: B

B^2 - (B-1)B + 1
=B2 - B^2 + B + 1
=B + 1 = N

Hence, as suspected, all numbers above 2 do have 3-digit palindrome
representations in negative bases. It's interesting that they also often
appear to have palindrome representations when base is a factor of B or a
multiple of factors of B.

ie. for 137, negative base palindromes occur when radix is in {-4, -9,
-17, -34, -68, -136}

136 factors to 2 * 2 * 2 * 17. All of the above, except -9, have factors
of 2 and/or 17. It also looks like base = B/2 is always a palindrome,
although I haven't worked out that algebra yet.

Update:
Here's the algebra. Base b/2 is always a palindrome for odd numbers, N.

Let b = (N-1) as before...

Then the base b/2 palindrome is
(b/2)^2 - [(b/2)-2](b/2) + 1
=b^2/4 - b^2/4 + 2b/2 + 1
=b+1=N

So the general form is [1][(N-1)/2][1]

In the case of 137, above, to check backwards,
1,[((137-1)/2)-2],1 had better be 137 in base (137-1)/2.

137-1 = 136; 136/2 = 68

[1][66][1]
= 68^2 - 66*68 + 1
= 137

Good.

So since all primes > 2 are odd, all primes > 2 will have a minimum
of 2 palindrome representations. (so far)
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TrivialPal071806
Jul_14_2006

Correction. 6 is a 3 digit palindrome in base -5 (141). I didn't check
enough bases.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SixPal071406
Jul_14_2006

Overnight, the primes got down to 79627 without finding a non-palindrome.
It's a little surprising that it doesn't even look like I need the
positive bases. Every prime after 2, up to 79627 has a palindrome
representation in just the negative bases.

For all numbers, I'm somewhere in the mid-20 thousands and haven't found
any new non-palindromes after 6. I'll leave it running 'til the sysadmin
at school decides to kill it for using up the cpu, but I don't think I'm
gonna find any non-palindrome numbers. That data's not saved, so I can't
look for maximum's or to see if I need the positive bases. Have to save
those questions for later.

Here's another sequence not at AT&T (http://www.research.att.com/~njas/sequences/)
7,11,17,31,53,61,101,113,131,137,173,181,223,257,311,331,367,409,449,457,...

Primes with 5 digit palindromes in negative bases. (It looks like just
about all of them have 3 digit palindromes... 4 digits are negative
numbers... 5 is apparently the first "interesting" one.)

Here's one to spot-check... 457: [1][1][0][1][0][1][1]_-3,
[1][7][0][7][1]_-8, [2][9][2]_13, [1][5][1]_19, [1][5][1]_-24,
[1][26][1]_-38, [1][49][1]_-57, [1][70][1]_-76, [1][110][1]_-114,
[1][149][1]_-152, [1][226][1]_-228, **229( 17261 / 18102 ) : 11

So the 5 digit palindrome is 17071_(-8).
= 1*8^4 + 7*8^(-3) + 0*8^2 + 7*8 + 1
= 4096 - 3584 -56 + 1
= 457

Matches. Good. I don't yet trust this conversion program, although all
my spotchecks have come up right so far.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NegPal071406
Jul_14_2006

Well there's still lots of margin for error, but with help from google...
http://groups.google.com/group/alt.math.recreational/browse_frm/thread/d8fd9d49139cfa90/8c81fb28099730b2?tvc=1&

And wikipedia...
http://en.wikipedia.org/wiki/Negabinary

I think I've got a very (VERY VERY VERY) sloppy and crude base conversion
going for positive and negative bases.

Thus far, the only prime which is not a palindrome in some base, positive
or negative, is 2. (not counting 1_2 & 11_1, of course) The only positive
numbers which aren't palindromes, up to a few thousand, are 1, 2 and 6.

I killed the other trial around 40 million. The ratio of
prime_palindromes/all_primes in the positive bases was somewhere around
94.18% when I killed it. I'm convinced it was growing towards 1, but I'd
like to see it happen (on a faster computer than my laptop). I still have
the data. Maybe I'll write up a summary and post it some day, just for
fun. The most palindromes I found for any number was 29. I'm still
intrigued by the fact that in base 10, all the 20-somethings I found
(above 20) ended in 1.

Now we see what happens with negative bases added into the mix.

Spot check. My program says 19291_(-10) is a palindrome for 1111_10.
Let's see...

10,000 + 9(-1,000) + 2(100) + 9(-10) + 1
=1,000 + 200 - 90 + 1
=1,111

Correct. Phew.

Long past time for bed now. Running just the primes on my laptop. I'll
revisit primes + composites later. Primes are up to 20771 with no
palindromes found besides 2.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PalAgain071306
Jul_11_2006

Hmmm... The first non-palindrome primes in positive bases turn out to
have palindrome representations in negative bases.

3 - 111 base (-2)
11 - 11111 base (-2)
19 - 131 base (-6)
47 - 313 base (-4)

I wonder if any integers above 2 actually lack 3+ digit palindrome
representations if we include positive and negative bases. I'm thinking
maybe not.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NegBase071106
Jul_11_2006

Today we found 35814241. A prime with 29 palindromic representations.
Palindrome_primes/all_primes is 94.127% at 3657331. Apparently still
growing. All primes found with 21 or more palindrome representations
still end with 1. (Base 10; 106 of them. I know I said 127 yesterday.
Don't know what I was looking at, but I was wrong). Still two primes
with 20 palindrome representations ending with 9.

36573071 is the biggest prime with no palindromes besides 1 and 11.

Maximum gaps between non-palindromes are unchanged at 238 palindrome
primes or 3834 integers.

Here are the palindromic representations for 35814241.

35814241: [279][157][279]_358, [34][227][34]_1023, [29][717][29]_1099,
[3][2987] [3]_2993, [1][4159][1]_4256, [1][4076][1]_4284,
[1][3771][1]_4389, [1][3492][1]_ 4488, [1][3398][1]_4522,
[1][3294][1]_4560, [1][3132][1]_4620, [1][2764][1]_4760 ,
[1][2692][1]_4788, [1][2547][1]_4845, [1][2419][1]_4896,
[1][2124][1]_5016, [1 ][2066][1]_5040, [1][1762][1]_5168,
[1][1604][1]_5236, [1][1503][1]_5280, [1][14 12][1]_5320,
[1][1333][1]_5355, [1][1073][1]_5472, [1][916][1]_5544, [1][774][1] _5610,
[1][558][1]_5712, [1][346][1]_5814, [1][268][1]_5852, [1][1][1]_5984,
**5984( 2064380 / 2193592 ) : 29

(Just for fun, I spot checked the base 4788 numeral. According to
my Windows calculator, 4788^2 + (2692 * 4788) + 1 is equal to 35814241,
as hoped.)

Oh. And most important of all... zero episodes of spontaneous laptop
combustion.
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#XXIXdigits071106
Jul_10_2006

Another sequence AT&T doesn't seem to have... (if I printed it right)

0, 0, 2, 2, 6, 0, 5, 4, 5, 0, 0, 2, 0, 1, 6, 7, 0, 3, 0, 1, 1, 2, 2,
0, 3, 7, 8, 8, 0, 3, 2, 8, 10, 12, 2, 3, 13, 0, 1, 2, 4, 1, 16, 2,
4, 15, 7, 0, 0, 2, 7, 4, 3, 13, 3, 5, 0, 17, 3, 4, 0, 2, 5, 3, 1, 0,
3, 4, 1, 10, 2, 2, 12, 4, 3, 15, 3, 0, 2, 3, 4, 17, 7, 6, 7, 1, 12,
1, 1, 6, 6, 3, 2, 14, 1, 2, 4, 2, 21, 0, 19, 7, 1, 1, 4, 1, 3, 11,
3, 0, 0, 3, 8, 7, 1, 9, 5, 4, 4, 8, 3, 0, 1, 12, 0, 1, 1, 3, 8, 4,
6, 0, 0, 3, 1, 4, 1, 4, 4, 3, 12, 5, 1, 7, 4, 0, 13, 8, 1, 1, 0, 4,
6, 4, 0, 2, 1, 3, 4, 1, 4, 12, 6, 3, 17, 9, 5, 6, 0, 3, 5, 6, 5, 4,
1, 12, 5, 27, 11, 6, 8, 1, 3, 3, 2, 4, 0, 7, 3, 3, 0, 0, 11, 11, 2,
10, 4, 10, 9, 6, 11, 1, 0, 9, 4, 1, 3, 6, 0, 3, 4, 0, 13, 3, 6, 4,
4, 4, 13, 15, 0, 3, 6, 5, 0, 18, 9, 5, 3, 3, 9, 9, 4, 4, 0, 5, 8, 6,
10, 0, 7, 6, 0, 11, 1, 5, 13, 12, 10, 12, 0, 10, 24, 1, 7, 9, 0, 13,
2, 1, 1, 4, 2, 1, 2, 8, 3, 0, 0, 1, 9, 4, 7, 4, 6, 18, 3, 4, 1, 2,
0, 8, 3, 1, 5, 0, 6, 19, 25, 0, 23, 3, 0, 4, 33, 10, 20, 1, 15, 23,
31, 11, 4, 15, 3, 0, 6, 16, 15, 1, 4, 9, 3, 13, 3, 3, 16, 25, 20, 4,
3, 9, 12, 3, 6, 13, 0, 1, 9, 8, 5, 16, 13, 4, 8, 4, 2, 0, 2, 11, 15,
21, 3, 6, 2, 3, 2, 13, 5, 1, 6, 19, 7, 0, 1, 5, 2, 4, 8, 0, 7, 8, 1,
4, 1, 1, 0, 12, 4, 7, 32, 3, 6, 3, 17, 4, 0, 4, 12, 12, 1, 5, 6, 35,
10, 0, 12, 8, 0, 31, 20, 1, 10, 3, 8, 21, 5, 10, 10, 0, 3, 4, 6, 15,
18, 2, 1, 10, 6, 9, 1, 36, 2, 2, 4, 1, 1, 4, 9, 1, 7, 5, 9, 16, 10,
19, 1, 1, 14, 8, 12, 9, 5, 0, 7, 1, 2, 0, 8, 1, 9, 0, 6, 15, 6, 13,
9, 4, 0, 2, 1, 2, 8, 16, 22, 4, 10, 8, 0, 13, 5, 25, 12, 5, 8, 2, 0,
0, 27, 2, 16, 1, 39, 1, 5, 12, 4, 4, 12, 5, 8, 1, 12, 3, 3, 3, 9, 7,
0, 11, 13, 8, 2, 6, 4, 3, 2, 7, 7, 3, 1,

Number of palindrome primes in between consecutive non-palindrome
primes... The leading 0 is optional since 2 is the first prime.

i.e. 2,3,_5_,_7_,11,_13_,_17_,19,_23_,_29_,_31_,_37_,_41_,_43_,47,53

No palindromes before 2 - 0
No palindromes before 3 - 0
5,7 - 2
13,17 - 2
23,29,31,37,41,43 - 6
no primes between 47 & 53 which are not palindromes. - 0
...
etc...
...

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Sequence071006
Jul_10_2006

Today we (my laptop and I) found 31600801, a prime with 27 palindromic
representations. The most for any prime up to 32.7 million. We also
noticed something a little surprising. So far, all primes with 21
palindrome representations or more (127 of 'em) end in 1. The only two
with 20 palindromic representations end in 9. They are 19027009 and
28756729. Oh. The ratio of prime_palindromes/all_primes is over 94% and
apparently still growing too. No changes in the maximum gaps between
non-palindromes.

14414401(24) and 28828801(26) are fun looking numerals.

Good thing my laptop's not a Dell. I'd hate to have it burst into flames
while I'm not here to extinguish it. Call me paranoid, but I'm thinking
of putting an end to this experiment for safety reasons. ;-) This poor
little laptop has been getting quite a workout. The CPU's a little warm
on my lap.



Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwentyOneReps071006
Jul_09_2006

The largest number of palindromic primes in between two primes with no
palindrome representations (other than 1 and 11) appears to be 238 for
primes up to 29.6 million or so. 22312319 (no palindromes) is followed by
238 palindrome primes before 22316153 (no palindromes) is encountered.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeInterval070906
Jul_08_2006

Here's another sequence AT&T doesn't have...

1, 8, 8, 28, 6, 26, 24, 34, 2, 10, 14, 4, 12, 44, 40, 6, 14, 10, 18,
6, 30, 12, 8, 22, 50, 52, 72, 6, 24, 14, 52, 80, 88, 26, 24, 100, 6,
14, 22, 30, 12, 126, 26, 24, 130, 66, 6, 8, 12, 52, 42, 26, 90, 40,
44, 6, 148, 42, 44, 4, 14, 52, 24, 12, 12, 26, 42, 28, 80, 22, 30,
78, 42, 44, 154, 20, 6, 10, 20, 36, 148, 66, 60, 66, 30, 110, 24,
6, 64, 48, 36, 42, 98, 12, 24, 40, 20, 190, 14, 160, 66, 18, 8, 40,
18, 54, 72, 54, 2, 10, 42, 72, 60, 26, 94, 36, 50, 58, 84, 38, 10,
14, 78, 10, 18, 20, 40, 80, 52, 66, 6, 6, 42, 36, 30, 14, 40, 32,
24, 126, 40, 18, 80, 36, 12, 100, 108, 20, 12, 10, 42, 68, 30, 18,
22, 8, 34, 32, 16, 30, 162, 48, 54, 140, 78, 76, 36, 8, 28, 60, 80
...
...

Gaps between primes which are not 3+ digit palindromes in any base.

i.e. 2,3,11,19,47,53,79,103,137,139,149,163,167,179,223,263,...

It's also interesting and a little surprising that the most common bases
are not the smaller ones. I guess that's because the aba format, 3 digit,
palindrome appears more often in bigger bases.

For example, I've found 776 base 10 palindromes and 4189 base 255
palindromes. I guess there are 100 aba or aaa palindromes in base 10 and
17547721 of them in base 4189 (prime + composite).


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NoPalGaps070706
Jul_08_2006

Up to around 25.5 million, the biggest (numeric) gap between two
consecutive non-palendrome primes is 3834 (22316153 - 22312319). Don't
know what the biggest number of palindromes between two non-palindromes
is. (93.8% palindromes at 25537103)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#ZeroGaps070706
Jul_07_2006

93.68% of primes up to somewhere just below 22 million have palindrome
representations... Two with 26, one with 25, etc... Here are the top 10
and the biggest non-palindromes.

20180161 23
21252001 23
14414401 24
14608441 24
16511041 24
17907121 24
18849601 24
18960481 25
15135121 26
21067201 26

21906767: **4680( 1296318 / 1383711 ) : 0
21906883: **4680( 1296322 / 1383716 ) : 0
21907229: **4680( 1296340 / 1383735 ) : 0
21907517: **4680( 1296352 / 1383748 ) : 0
21907559: **4680( 1296355 / 1383752 ) : 0

And here are the 26 representations for 21067201. Three digits for all...

21067201: [32][153][32]_809, [21][703][21]_985, [14][957][14]_1193,
[1][3084][1] _3300, [1][3011][1]_3325, [1][2956][1]_3344,
[1][2910][1]_3360, [1][2740][1]_342 0, [1][2615][1]_3465,
[1][2465][1]_3520, [1][2252][1]_3600, [1][2127][1]_3648,
[1][2004][1]_3696, [1][1838][1]_3762, [1][1744][1]_3800,
[1][1622][1]_3850, [1][1360][1]_3960, [1][1290][1]_3990,
[1][1193][1]_4032, [1][860][1]_4180, [1][816][1 ]_4200,
[1][694][1]_4256, [1][653][1]_4275, [1][411][1]_4389,
[1][388][1]_4400, [1][60][1]_4560, **4589( 1249276 / 1333978 ) : 26

The last one to date in base 10 was 9989899.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwentyTwoMillion070706
Jul_06_2006

Oh. While I'm at it. I'm up to 17146781 looking for palindromes. Here
are the top 10 or so...

13305601 21
13970881 21
14220361 21
14479921 21
15495481 21
15855841 21
16576561 21
16936921 21
17117101 21
13759201 22
15069601 22
14414401 24
14608441 24
16511041 24
15135121 26

Here's the highest non-palindrome...
17145103: **4140( 1028200 / 1100038 ) : 0

93.46% palindrome density and apparently still growing.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimePals070606
Jul_06_2006

Defining prime density as the ratio of primes / total results of a
function, I wonder if there's a catalog of prime density of functions...

For example, Euler's equation
1x^2 + 1x + 41 gives back 26.10% primes with x from 1 to 999999

Similarly,
3x^2 + 3x + 23 gives back 21.22% primes and
x^2 + 3x + 43 gives back 26.10% too.

Many functions give back 0, I'm sure.

wikipedia says there are no polynomials that give all primes, so the
answer to my earlier question about strings yielding a prime in every base
is "no". But, next question... are there any polynomials who's prime
density grows as x does? This might also be useful.

This catalog would take some serious horsepower to build. Even just for
polynomials with 1 variable. It would go something like this...

10 polynomials
1.) Check 1 coefficient polynomials in c={1->9} for x=1..10^1-1
10000 polynomials
2.) Check 2 coefficient polynomials in c1,c2={1->99,1->99} for x=1..10^2-1
100 polynomials
3.) Check 1 coefficient polynomials in c={10->99} for x=1..10^2-1
1000000000 polynomials
4.) Check 3 coefficient polynomials in c1,c2,c3={1->999, 1->999, 1->999} for x=1..10^3-1
1000000 polynomials
5.) Check 2 coefficient polynomials in c1,c2={1->999, 1->999} for x=1..10^3-1
1000 polynomials
6.) Check 1 coefficient polynomials in c={1->999} for x = 10^3-1
10000000000000000 polynomials
7.) Check 4 coefficient polynomials c#={1->9999} x=1..10^4-1
...
...etc...
...

This problem is pretty massive. Although I'm sure alot of them could be
quickly ruled out as 0%. Maybe just a catalog of interesting ones could
be saved.

My guess is that prime densities will shrink as x gets bigger, for all
polynomials, but it might be fun and interesting to play around.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeCats070606
Jul_05_2006

Up to 12156197, 21 is still the most palindrome representations for any
prime (4 have 21). 743026 palindromes out of 797630 total (0.9315).
12155849 is the biggest one with no palindrome representations.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PalProgress070506
Jul_03_2006

So I got up to
7174907: [11][710][11]_776, [11][80][11]_804, [8][129][8]_939, **2678(451983 / 487751 ) : 3

Before my disk quota got filled on the school computer. The ratio of
palindromes over all primes is up to 0.9266675. I'm wondering... if it
keeps approaching 1 forever, is there a "highest prime with no palindrome
representations"? I doubt it. That would mean that the number of
palindrome primes is the same as the number of non-palindrome primes.
That's still kind of hard to wrap my mind around.

Here are the top 10 primes up to 7174907, by number of palindrome
representations. (One with 19 eventually did show up).

1670761 18
2489761 18
4158001 18
4633201 18
5159701 18
6098401 19
3880801 20
4324321 20
4520881 20
5654881 21

Here are the 21 representations for 5654881. 3 digits each.

5654881: [91][51][91]_249, [37][293][37]_387, [5][903][5]_977,
[1][1677][1]_1683, [1][1453][1]_1760, [1][1383][1]_1785,
[1][1244][1]_1836, [1][1212][1]_1848, [1][1154][1]_1870,
[1][1102][1]_1890, [1][1066][1]_1904, [1][876][1]_1980, [1][789][1]_2016,
[1][732][1]_2040, [1][641][1]_2079, [1][498][1]_2142, [1][458][1]_2160,
[1][276][1]_2244, [1][169][1]_2295, [1][138][1]_2310, [1][4][1]_2376,
**2377( 361179 / 390695 ) : 21


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TopTenPals070306
Jul_01_2006

Found a prime with 20 palindromic representations... 3880801.

3880801: [1][20][25][20][1]_40, [28][185][28]_369, [25][302][25]_388,
[17][198][17]_472, [1][1372][1]_1400, [1][1255][1]_1440,
[1][1170][1]_1470, [1][980][1]_1540, [1][907][1]_1568, [1][889][1]_1575,
[1][866][1]_1584, [1][783][1]_1617, [1][702][1]_1650, [1][630][1]_1680,
[1][445][1]_1760, [1][436][1]_1764, [1][356][1]_1800, [1][252][1]_1848,
[1][91][1]_1925, [1][20][1]_1960, **1969( 253537 / 275324 ) : 20

It's unexpected that the first 20 appeared before the first 19. I still
haven't found any with 19 representations. Up to 4105553 and the ratio of
palindromes / total_primes is 0.9215. (267339/290126)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#TwentyPal070106
Jul_01_2006

Just happened to spot these scrolling past. 6 consecutive primes all
of which can't be represented as palindromes (other than 1 & 11).

3253177: **1803( 214878 / 233792 ) : 0
3253219: **1803( 214878 / 233793 ) : 0
3253223: **1803( 214878 / 233794 ) : 0
3253231: **1803( 214878 / 233795 ) : 0
3253241: **1803( 214878 / 233796 ) : 0

That seems to be an unusual occurrence.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#NoPals070106
Jul_01_2006

Up to 3206471, the maximum number of palindromic prime representations is
18. 1670761 (another cool number) and 2489761 both have 18.

The ratio of palindromes/primes is 0.9189 (211949/230648).

1670761: [1][6][7][0][7][6][1]_10, [114][13][114]_121, [64][73][64]_161,
[13][277][13]_348, [4][463][4]_591, [1][902][1]_918, [1][849][1]_936,
[1][823][1]_945, [1][803][1]_952, [1][618][1]_1020, [1][489][1]_1071,
[1][467][1]_1080, [1][438][1]_1092, [1][407][1]_1105, [1][258][1]_1170,
[1][214][1]_1190, [1][141][1]_1224, [1][66][1]_1260, **1292( 114972 /
126103 ) : 18

2489761: [79][83][79]_177, [43][227][43]_238, [5][324][5]_674,
[1][1103][1]_1120, [1][1044][1]_1140, [1][958][1]_1170, [1][883][1]_1197,
[1][781][1]_1235, [1][747][1]_1248, [1][716][1]_1260, [1][542][1]_1330,
[1][459][1]_1365, [1][452][1]_1368, [1][289][1]_1440, [1][254][1]_1456,
[1][198][1]_1482, [1][118][1]_1520, [1][36][1]_1560, **1577( 167094 /
182380 ) : 18

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Pal18reps070106
Jun_30_2006

Counting with "wc" against the previous data, I think I find 7483
non-palindrome primes and 71675 palindromes. So 90.44% with just a few
numbers higher than a million. It'll be handy to have that number for
comparison when the current run passes a million.

The current run is up to 317197 now. 24407 out of 27373 primes are
palindromic. 89.165%. Still growing. I'm guessing this number is
approaching 1.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PalCounts063006
Jun_30_2006

Palindrome primes do seem to behave the way I expected repunits would.
As the number gets bigger, so does the maximum number of palindromic (is
that a word?) representations... Here are the two primes < 1,000,000 with
the most palindrome representations. 15, not counting 11 in base P-1 or 1
in base P.

950041: [49][122][49]_138, [41][18][41]_152, [25][148][25]_192,
[19][177][19]_219, [16][151][16]_239, [1][669][1]_696, [1][577][1]_728,
[1][506][1]_754, [1][438][1]_780, [1][358][1]_812, [1][341][1]_819,
[1][291][1]_840, [1][222][1]_870, [1][134][1]_910, [1][79][1]_936, **974: 15

960961: [47][93][47]_142, [28][127][28]_183, [17][198][17]_232,
[1][661][1]_704, [1][629][1]_715, [1][592][1]_728, [1][478][1]_770,
[1][452][1]_780, [1][323][1]_832, [1][304][1]_840, [1][262][1]_858,
[1][212][1]_880, [1][146][1]_910, [1][116][1]_924, [1][41][1]_960, **980: 15

960961 is a pretty cool looking number too. : -)

Running again with a new counter. Down to 57179, 5033 primes have
palindromic representations and 766 do not. 87% can be represented as
palindromes. That percentage appears to be growing. Almost 88% now at
101939. Over 88% at 147557 (12022/13640).

*Of course, this all assumes bug-free code. Let the buyer beware.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MorePals063006
Jun_30_2006

So if I have an infinite sized, ordered digit list, which starts with 0-9
then A-Z than a-z then the rest of the list in any order. It seems that
"Steve" is never prime in any base (28x^4 + 55x^3 + 40x^2 + 57x + 40)...
No primes for "steve" or "dad" either I think. On the other hand, "DAD"
is prime in lots of bases. For example, the 2nd column below is a base
where DAD is prime.

(ie.. 13x^2 + 10x + 13; x={66,74,84,86,90,114,126...})
P: 66: 57301:
P: 74: 71941:
P: 84: 92581:
P: 86: 97021:
P: 90: 106213:
P: 114: 170101:
P: 126: 207661:

...
...

P: 4171514: 226219919393701:
P: 4171604: 226229680842661:
P: 4171620: 226231416233413:
P: 4171644: 226234019332021:
P: 4171680: 226237924008013:
P: 4171706: 226240744072741:

So the question is, is there a digit sequence (length greater than 1)
which is always prime, regardless of base? I'm thinking the answer must
be no or else finding big prime numbers would be trivial, but I'm not
clear why not yet.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeStrings063006
Jun_06_2006


Now I guess I'll have to generate all prime palindromes of 2 digits or
more in all bases.... As with repunits, all primes are palindromes with 1
digit, no sense listing the trivial cases. Here are the base 30
palindrome primes, AT&T doesn't have 'em. As with repunits, they have the
small bases.

Palendome primes in base 30...

Representation
B 10: Base 30
3: 3
5: 5
7: 7
11: B
13: D
17: H
19: J
23: N
29: T
31: 11
991: 131
1021: 141
1051: 151
1171: 191
1201: 1A1
1231: 1B1
1291: 1D1
1321: 1E1
1381: 1G1
1471: 1J1
1531: 1L1
1621: 1O1
1741: 1S1
6337: 717
6367: 727
6397: 737
6427: 747
6547: 787
6577: 797
6607: 7A7
6637: 7B7
6907: 7K7
6967: 7M7
6997: 7N7
7027: 7O7
7057: 7P7
7177: 7T7
9941: B1B
10061: B5B
10091: B6B
10151: B8B
10181: B9B
10211: BAB
10271: BCB
10301: BDB
10331: BEB
10391: BGB
10601: BNB
10631: BOB
10691: BQB
10781: BTB
11743: D1D
11833: D4D
11863: D5D
11923: D7D
11953: D8D
12043: DBD
12073: DCD
12163: DFD
12253: DID
12343: DLD
12373: DMD
12433: DOD
12553: DSD
12583: DTD
15377: H2H
15467: H5H
15497: H6H
15527: H7H
15647: HBH
15737: HEH
15767: HFH
15797: HGH
15887: HJH
16007: HNH
16067: HPH
16097: HQH
16127: HRH
16187: HTH
17209: J3J
17239: J4J
17299: J6J
17359: J8J
17389: J9J
17419: JAJ
17449: JBJ
17509: JDJ
17539: JEJ
17569: JFJ
17599: JGJ
17659: JIJ
17749: JLJ
17839: JOJ
17929: JRJ
17959: JSJ
17989: JTJ
20753: N1N
20873: N5N
20903: N6N
20963: N8N
21023: NAN
21143: NEN
21323: NKN
21383: NMN
21503: NQN
21563: NSN
26189: T2T
26249: T4T
26309: T6T
26339: T7T
26399: T9T
26459: TBT
26489: TCT
26669: TIT
26699: TJT
26729: TKT
26759: TLT
26849: TOT
26879: TPT

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimePals060606
Jun_06_2006


I've got a cold and I'm tired and my head's getting foggy, but I think
these are the number of ways primes can be represented as palindromes up
to 61753. That's about as high as I can go without actually thinking.
Plenty of room for error so far, I'll definitely need to look at this more
carefully.

[spalmer@taz cpp]$ ./palprime | awk '{print $NF}' | sort | uniq -c | sort -=
n
1 10
1 9
5 8
21 7
79 6
204 5
516 4
808 0
1113 3
1723 2
1742 1

Here are the ones with 9 or 10 palindrome representations...

[spalmer@taz cpp]$ ./palprime | egrep ': (9|10)$'
54121: PQP_46, ONO_47, LWL_50, EXE_61, B3B_70, 9S9_76, 7D7_87, 1=C51_165, 1=
x1_205, 1Q1_220, : 10
57601: bXb_39, Q3Q_47, M7M_51, 7r7_87, 1=AE1_180, 11_192, 1/1_200, 1V1_225,=
101_240, : 9

Here are some of the prime numbers which are not representable as
palindromes of more than 2 digits.

[spalmer@taz cpp]$ ./palprime | egrep ': 0$' | head -20
2: : 0
3: : 0
11: : 0
19: : 0
47: : 0
53: : 0
79: : 0
103: : 0
137: : 0
139: : 0
149: : 0
163: : 0
167: : 0
179: : 0
223: : 0
263: : 0
269: : 0
283: : 0
293: : 0
311: : 0

Here are the first 40 primes and their palindrome representations of 3 or
more digits....

[spalmer@taz cpp]$ ./palprime | head -40
2: : 0
3: : 0
5: 101_2, : 1
7: 111_2, : 1
11: : 0
13: 111_3, : 1
17: 10001_2, 101_4, : 2
19: : 0
23: 212_3, : 1
29: 131_4, : 1
31: 11111_2, 111_5, : 2
37: 101_6, : 1
41: 131_5, : 1
43: 111_6, : 1
47: : 0
53: : 0
59: 323_4, : 1
61: 141_6, : 1
67: 232_5, 151_6, : 2
71: 131_7, : 1
73: 1001001_2, 111_8, : 2
79: : 0
83: 313_5, : 1
89: 131_8, : 1
97: 141_8, : 1
101: 101_10, : 1
103: : 0
107: 1101011_2, 212_7, : 2
109: 414_5, 131_9, : 2
113: 161_8, : 1
127: 1111111_2, 151_9, : 2
131: 131_10, : 1
137: : 0
139: : 0
149: : 0
151: 12121_3, 151_10, : 2
157: 313_7, 111_12, : 2
163: : 0
167: : 0
173: 20102_3, 212_9, : 2

AT&T has the sequence 5,7,13,17,23,29,31,37,... which is reassuring 'cause
it makes my code a bit more believable. Primes which are palindromes in
more than 1 base... A087155 - http://www.research.att.com/~njas/sequences/=
?q=3D5%2C7%2C13%2C17%2C23%2C29%2C31%2C37%2C41%2C43&sort=3D0&fmt=3D0&languag=
e=3Denglish&go=3DSearch

They don't seem to have the complementery sequence, which is
2,3,11,19,47,53,57,... primes which have no non-trivial palindrome
representations. (trivial being 1 & 11 again).



And here's the code...

[spalmer@taz cpp]$ cat palprime.cpp
#include
#include
#include "Integer.h"
#include "mymath.h"
#include
#include "bconlib.h"

using namespace std;
bool ispal ( char * );

bool ispal (char * word)
{
int end=3Dstrlen(word);

for (int lcv=3D0; lcv {
if ( word[lcv] !=3D word[end] )
{
return false;
} else {
if ( lcv =3D=3D end ) return true;
}
}
}

int main()
{
for ( Integer lcv=3D2; lcv<61753; lcv++ )
{
Integer count =3D 0;
Integer BASE;
if ( isprime (lcv))
{
cout << lcv << ": ";
for ( BASE=3D2; BASE<248 && BASE < sqrt(lcv) + 1; BASE++ )
{
if ( ispal ( dec2str ( lcv, BASE, DIGITS )))
{
cout << dec2str (lcv, BASE, DIGITS) << "_" << BASE << ", ";
count++;
}
}
}
if ( isprime(lcv)) cout << ": " << count << endl;
}
}



--=20
Regards,
Steve Palmer
Unix & information technology specialist

http://home.ccil.org/~remlaps
e-mail: remlaps@ccil.org =09aim: remlaps@aol.com

"The knowledge of the natural principles is given to us by God, the
creator of our nature. The natural principles therefore are part of
God's wisdom. Whatever goes against the natural knowledge is against
God. Such a contradiction cannot have its origin in God."
=3D=3D> Thomas Aquinas (The Sum Against the Gentiles)

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PalPrimeCounts060606
Jun_06_2006

This is astonishing. I guess it shouldn't be. It should've been almost
obvious, but it wasn't to me. It looks as if all palindromes with even
numbers of digits in all bases are multiples of 11 in that base.

I don't quite have the proof yet, but it must be recursive. Base case 11,
22, 33, ... up to Base^2-1. We know those are palindromes and divisibile
by 11.

The inductive hypothesis will be to assume true for k pairs of digits.
Show true for k+1 pairs when you add the pair of digits 1 digit in front
and one in back. I'm thinking I remember something kind of like this in
CSC520, when we did Turing machines.

I'm not quite seeing the proof that the k+1 pair is divisible by 11, but
I'm thinking it'll be related to the fact that d##d is (1001 * d) + (base
* ##). ## is divisible by 11. 1001 is divisible by 11, so d00d is
divisible by 11. Those facts still need to be integrated and then
extended for more than 4 digits.

So I haven't proven it yet, but I'm convinced that if a number is a
palindrome and it has an even number of digits, it can't be prime.
Not there (wherever there is), but getting closer.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#EvenPrimePals11-060606
Jun_06_2006

Pulling out my rusty long division of polynomials from junior high (aided
by this web page: http://www.purplemath.com/modules/polydiv2.htm), I see that:

x^3 + 0x^2 + 0x + 1 / x+1 = x^2 - x + 1

Trying it in base 10, 1001 = 11 * (100 - 10 + 1) = 11 * 91.
Trying in base 2, 4 - 2 + 1 = 3, which is 11_2, so 11_2 * 11_2 = 1001_2

So that's why 1001 can never be prime. 11 is a factor of 1001 in every
base.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Algebra0606006
Jun_06_2006

So if the number of digits in a prime palindrome has to be odd, that would
mean that the simplest palindrome with an even number of digits (greater
than 2), 1001, can't be prime in any base. On the surface, I don't see
why that should be true, but it seems like it might be...

[spalmer@taz cpp]$ ./prime1001
Found: 1^3 + 1 ==> 2
Checked to: 100000
Checked to: 200000
Checked to: 300000
Checked to: 400000
Checked to: 500000
Checked to: 600000
Checked to: 700000
Checked to: 800000
Checked to: 900000
Checked to: 1000000
Checked to: 1100000
Checked to: 1200000
Checked to: 1300000
Checked to: 1400000
Checked to: 1500000
Checked to: 1600000
Checked to: 1700000
Checked to: 1800000
...
Checked to: 15100000
Checked to: 15200000
Checked to: 15300000
Checked to: 15400000
Checked to: 15500000
...

Here's the code.

[spalmer@taz cpp]$ cat prime1001.cpp
#include < iostream >
#include < math.h >
#include "Integer.h"

using namespace std;

int main()
{
for ( Integer lcv=1; lcv < 100000000; lcv++ )
{
Integer itest = lcv * lcv * lcv + 1;
if ( isprime (itest))
cout << "Found: " << lcv << "^3 + 1 ==> "
<< itest << endl;

if (0 == (lcv % 100000))
cout << "Checked to: " << lcv << endl;
}
}


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimePals1001-060606
Jun_06_2006

Palindrome (not palendrome) primes < 10000 with 7 palindrome
representations (the most < 10000). There's 8191 again. Interesting that
all 3 of them show up in base 33.


[spalmer@taz cpp]$ ./palprime | egrep -v Checking | egrep '4591|7993|8191'
Base: Dec#: Palindrome : Number of
Base Digits
2: 8191: 1111111111111: 13
8: 7993: 17471: 5
19: 4591: CDC: 3
20: 4591: B9B: 3
24: 4591: 7N7: 3
26: 7993: BLB: 3
33: 4591: 474: 3
33: 7993: 7B7: 3
33: 8191: 7H7: 3
37: 4591: 3D3: 3
46: 8191: 3e3: 3
47: 7993: 3T3: 3
51: 4591: 1d1: 3
54: 4591: 1V1: 3
61: 7993: 292: 3
65: 8191: 1z1: 3
70: 8191: 1l1: 3
72: 7993: 1d1: 3
74: 7993: 1Y1: 3
78: 8191: 1R1: 3
90: 8191: 111: 3



Also, it occurred to me that repunits are just a special case of
palindromes. Last, it looks like (maybe) palindromes have to have an odd
number of digits (after 2) in order to be prime. I've seen some with 9,
15 or 21 digits, so the number of digits does not need to be prime.


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimePals2-060606
May_18_2006

Found this page...
http://my.tbaytel.net/forslund/integers.html

Which says "31 and 8191 are the only two known numbers (N) that have 3
different cases of the following relation. All the rest have only one or
two such cases. Notice that 31 and 8191 are the 3rd and 5th Mersenne
primes respectively.
N = (bn - 1)/(b - 1) for 1 < b < N and n > 1
Aside: N is the n-digit number in base b with all digits equal to 1."

Looks like I need look no further. Good thing 'cause my composite check
died at 95569.

95669 --> 0: 0 1: 95274 2: 391 3: 2 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0

391 out of 95669 numbers are representable as repunits. I'm thinking my
number of digits test will not be an effective screen. Oh well. It was
fun exploring.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CompositeDone051806
May_18_2006

Out to 86888, all numbers... prime and composite... 86512 trivial only
repunits. 372 with 1 non-trivial repunit representation and 2 with 2
non-trivial repunit representations. (1 & 2 not included)

86888 --> 0: 0 1: 86512 2: 372 3: 2 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0

Not looking promising to use the number of digits as a screen for primes.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CompositeRep1s051806
May_17_2006

Up to 124153 still only 2 numbers with multiple non-trivial repunit
representations.

================== Wed May 17 19:58:08 EDT 2006 =========================
2: 0
31: 3
8191: 3
124153: 1
===================================================
0: 1
1: 11605
2: 88
3: 2
4: 0
5: 0
6: 0
7: 0
8: 0
===================================================
7,13,43,73,127,157,211,241,307,421,463,601,757,1093,1123,1483,1723,2551,2801,2971,3307,3541,3907,4423,4831,5113,5701,6007,6163,6481,8011,9901,10303,11131,12211,12433,13807,14281,17293,19183,19531,20023,20593,21757,22621,22651,23563,24181,26083,26407,27061,28057,28393,30103,30941,31153,35533,35911,37057,37831,41413,42643,43891,46441,47743,53593,55933,55987,60271,60763,71023,74257,77563,78121,82657,83233,84391,86143,88741,95791,98911,108571,110557,113233,117307,118681,121453,123553

===================================================

Incidentally, if we put 31 and 8191 into that list and plug it into AT&T
we get...

http://www.research.att.com/~njas/sequences/?q=7%2C13%2C31%2C43%2C73%2C127%2C157%2C211%2C241%2C307%2C421%2C463%2C601%2C757%2C1093%2C1123%2C1483%2C1723%2C2551%2C2801%2C2971%2C3307%2C3541%2C3907%2C4423%2C4831&sort=0&fmt=0&language=english&go=Search

"Primes of the form 1+n+n^2+n^3+ ... +n^k, n > 1, k > 1."

So they do already have the non-trivial repunits in sequence, ordered by
numeric value.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#LotsFasterNow021706
May_17_2006

AT&T does not have a sequence that begins with 31 & 8191. Numbers with
multiple (non-trivial) repunit representations.

http://www.research.att.com/~njas/sequences/?q=31%2C8191&language=english&go=Search

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FYISequence051706
May_17_2006

A slightly less naive method is much much faster. Out to 13177 in a
matter of minutes. Found another one with 2 non-trivial representations.
Curiously, one less than a power of two again. Up to 36 with a single
non-trivial representation.

================== Wed May 17 06:32:03 EDT 2006 =========================
2: 0
31: 3
8191: 3
13177: 1
===================================================
0: 1
1: 1547
2: 36
3: 2
4: 0
5: 0
6: 0
7: 0
8: 0
===================================================
7,13,43,73,127,157,211,241,307,421,463,601,757,1093,1123,1483,1723,2551,2801,2971,3307,3541,3907,4423,4831,5113,5701,6007,6163,6481,8011,9901,10303,11131,12211,12433
===================================================


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FasterNow051706
May_16_2006

It hit me the other morning. It should have been obvious that when a
repunit has a prime number of digits, it does not mean that the repunit is
prime.

I haven't proved it or found it proved, but it's starting to make sense.
I'm convinced it's true that a composite number of digits means a repunit
is composite. More specificially, it means that the repunit has a factor
which is also a repunit in the same base.

On the other hand, a prime number of digits simply means that the repunit
doesn't have any repunit factors (in the same base). It doesn't say
anything at all about factors which are not representable as repunits in
the current base.

For example, 57 = 111_7. 3 ones. 3 is prime. 11_7 = 8. 8 is not a
factor of 57. 19 & 3 are factors of 57. Neither is a repunit in base 7.
(25_7 & 3_7, resectively). On the other hand, I don't know what 1111_7
is, but I bet 11_7 (8) is a factor of it since 2 is a factor of 4. Let's
see....

1111_7 = 400 = 8 * 50 = 11_7 * 101_7

Incidentally, I guess I really didn't need to figure out what 1111_7 was.
11 * 101 = 1111 in any (integer) base, not just 7. These numbers really
are fascinating.

So any number that can be represented as 1111 in some base is not prime.
Same with 111111, 11111111, 111111111, 1111111111, etc... We just ruled
out a whole lot of numbers without any need for (explicit) factoring.

So the question, I think is this... is there a computatationally
efficient way to find all repunit representation of a given number. The
naive method I have been running since last week isn't going to cut it.
5 or so days to check not quite 7500 numbers.

And what that really means, is can we find all solutions to a set of
equations in parallel or recursively.

(*
* all x's are not the same up to j somewhat < N, the number being
* checked.
*)
x + 1 = N
x^2 + x + 1 = N
x^3 + x^2 + x + 1 = N
...
...
x^j + x^(j-1) + ... + x^2 + x + 1 = N

If we build the list of solutions to those equations, it may be faster to
count digits and check those counts for primacy, potentially eliminating
the need to factor. Can't prove a number is prime any faster, but there
might be numbers which could be proved composite this way faster than
factoring. Dunno. For any of this to be of any use, I think my guess
would have to be right. We need really big numbers to have lots of
repunit representations in different bases. So far in my trials I'm not
seeing it.

Up to 7489. 917 trivial-only prime repunits. 30 primes with 1
non-trivial repunit representation, still just 31 with 2 non-trivial
representations.

If that trend continues, I don't see the digit count being a useful
screen. We'll see. I think I'm in over my head...

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeScreen051606
May_15_2006

I'm up to 7193. 31 is still the only one with more than 1 non-trivial
repunit representation. I think I'm going to have to actually think about
the method if I'm ever going to get to check some bigger numbers...

So far, 1 prime not representable as a repunit (2) in base 2 or higher,
887 primes only representable as 11 in some base. 30 with 1 non-trivial
representation and 1 with 2 non-trivial representations.

================== Mon May 15 20:04:38 EDT 2006 =========================
2: 0
31: 3
7193: 1
===================================================
0: 1
1: 887
2: 30
3: 1
4: 0
5: 0
6: 0
7: 0
8: 0
===================================================
7,13,43,73,127,157,211,241,307,421,463,601,757,1093,1123,1483,1723,2551,2801,2971,3307,3541,3907,4423,4831,5113,5701,6007,6163,6481
===================================================


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#UpdateRep1051506
May_13_2006

Down to 6491 I've got 30 primes with a non-trivial repunit representation.
Still 1 with 2 representations.

================== Sat May 13 15:29:24 EDT 2006 =========================
2: 0
31: 3
6491: 1
===================================================
0: 1
1: 810
2: 30
3: 1
4: 0
5: 0
6: 0
7: 0
8: 0
===================================================
7,13,43,73,127,157,211,241,307,421,463,601,757,1093,1123,1483,1723,2551,2801,2971,3307,3541,3907,4423,4831,5113,5701,6007,6163,6481
===================================================


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Rep1Stats051306
May_13_2006

A graph of prime densities appears about 2/3 of the way down on the link
below. It looks more or less like I imagined I think.
http://primes.utm.edu/howmany.shtml

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeDensity051306
May_13_2006

So I'm thinking that as the number gets bigger, the number of repunit
representations should get bigger too. With the small numbers I'm looking
at, the non-trivial representations are infrequent, but as the numbers get
bigger and the density of the primes gets smaller, repunit representations
ought to get more common. This is because the options for base and number
of digits gets bigger along with the number.

So... As the primes become less frequent on the number line, they get
repeated more and more often when looking at the repunit matrix by base
and number of digits. I'm still not seeing the whole thing, but I'm
thinking there's a long shot that this property might be useful in a
prime number screen.

Something like to find if a number, N, is prime...

  • 1. write down all the non-trivial repunit representations of N.
  • 2. Check to see if any of the non-trivial ones have a prime
    number of ones.
  • 3. If not, N is not prime.
  • 4. If all of them do, N might be prime. Apply another test.


111_4 shows that having a prime number of one's in all repunit
representations is not sufficient to show a number prime by itself.

111_4 = 4^2 + 4 + 1 = 16 + 4 + 1 = 21--> Not prime, even though
the number of 1's is prime.
21 < 11111_2 && 21 > 1111_2
21 < 1111_3 && 21 > 111_3
21 = 111_4
21 < 111_5 && 21 > 11_5
21 < 111_6 && 21 > 11_6
21 < 111_7 && 21 > 11_7
21 < 111_8 && 21 > 11_8
21 < 111_9 && 21 > 11_9
...
It should be apparent that once we pass 111_4, the only possible remaining
repunits are 11_20 1_21. Both are trivial. Therefore, having composite
numbers of ones can (I believe) rule a number out as a prime, but all prime
repunit representations still cannot rule one in. Nothing's changed from
when I wrote about that before. What's new is that I'm thinking the
number of times big numbers appear on the repunit table gets bigger as
the number gets bigger. It might be easier to find composite numbers of
ones in big repunits than to find factors in big numbers. Don't know yet.

I'm thinking writing down the repunit representations might be as difficult
as factoring. I'm still not seeing this as having much potential, but it's
entertaining.

Also, I'm thinking the 'density' of prime numbers acts an awful lot like a
first derivative. I wonder what the graph of density of primes over the
number line looks like? I'll have to look for that when I get some time
later. At 1 it's 0, then at 2 & 3, it's 50%, & 67%. At 4 it's back to
50%, then 60% at 5, 50% at 6 and so on. Generally approaching 0 with
slight bumps every time a new prime is encountered.

On the other hand, I think the number of repunit representations should
approach infinity. I can't see any reason (yet?) that there shoud be an
upper boundary on it. Of course, that's true for composites too, so I
am not sure how useful that fact might be.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeTest051306
May_12_2006

Up to 6091, still only 1 prime, 31, with more than 1 repunit
representation. I am starting to wonder if there is something special
about 31. I wonder how long my program will keep running before a
sysadmin decides its a zombie and kills it. Hopefully, summer break will
protect it. We'll see.

Here are the new ones with 1 non-trivial repunit (I have no idea what the
bases or lengths are. Didn't think to save them. I can go back and check
without much trouble if I am ever inclined to.)

4831: 2
5113: 2
5701: 2
6007: 2

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MultiPrimeRep1051206
May_11_2006

Follow-up to: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Diagonals051106

Well, duh! Of course they're the same series.

n^n-1/n-1

n^n = 1 followed by n 0's.
n^n - 1 = (n-1 digit) n times.
n^n-1/(n-1) = 111...1111 for n ones.

Just had to think a little tiny bit. Guess I can go kill that job now.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#FollowUp051106
May_11_2006

Prime repunits such that the number of digits is the same as the base.

[spalmer@taz cpp]$ ./diagRep1 | egrep prime
( 2, 2 ): 3 is prime.
( 3, 3 ): 13 is prime.
( 19, 19 ): 109912203092239643840221 is prime.
( 31, 31 ): 568972471024107865287021434301977158534824481 is prime.

Looks like AT&T has the base/number of digits, but not the primes.
(They have 2,3,19,31 and they add 7547. They don't have 3,13,
109912203092239643840221, 568972471024107865287021434301977158534824481.)
http://www.research.att.com/~njas/sequences/?q=2%2C3%2C19%2C31&language=english

They label it as "numbers n such that (n^n-1)/(n-1) is prime", so I'm not
really sure it's the same sequence, but I bet it is.

I'm checking to see if 7547 1's in base 7547 is a prime now. Don't know
how long that will take, or even if it will finish.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Diagonals051106
May_11_2006

Two more orderings of all prime repunits, more directly modelled after
Cantor. x-axis = number of digits with 2 on the left, value increasing to
the right. y-axis = radix, 2 at top with the value increasing downward.
Earlier orderings were growing squares from the origin. These are growing
triangles the way Cantor did. These aren't in the Online Encyclopedia of
Integer Sequences either.

/*
* Move down first, then diagonally up & to the right, then right, then
* diagonally down & to the left. Repeat.
* Print primes in the order found.
*/
( 2 ones, base: 2 ) 3 is prime.
( 3 ones, base: 2 ) 7 is prime.
( 3 ones, base: 3 ) 13 is prime.
( 2 ones, base: 4 ) 5 is prime.
( 5 ones, base: 2 ) 31 is prime.
( 3 ones, base: 5 ) 31 is prime.
( 2 ones, base: 6 ) 7 is prime.
( 3 ones, base: 6 ) 43 is prime.
( 7 ones, base: 2 ) 127 is prime.
( 7 ones, base: 3 ) 1093 is prime.
( 3 ones, base: 8 ) 73 is prime.
( 7 ones, base: 5 ) 19531 is prime.
( 5 ones, base: 7 ) 2801 is prime.
( 2 ones, base: 10 ) 11 is prime.
( 7 ones, base: 6 ) 55987 is prime.
( 2 ones, base: 12 ) 13 is prime.
( 3 ones, base: 12 ) 157 is prime.
( 13 ones, base: 2 ) 8191 is prime.
( 13 ones, base: 3 ) 797161 is prime.
( 11 ones, base: 5 ) 12207031 is prime.
( 3 ones, base: 14 ) 211 is prime.
( 5 ones, base: 12 ) 22621 is prime.
( 13 ones, base: 5 ) 305175781 is prime.
( 5 ones, base: 13 ) 30941 is prime.
( 3 ones, base: 15 ) 241 is prime.
( 2 ones, base: 16 ) 17 is prime.
( 17 ones, base: 2 ) 131071 is prime.
( 13 ones, base: 7 ) 16148168401 is prime.
( 7 ones, base: 13 ) 5229043 is prime.
( 3 ones, base: 17 ) 307 is prime.
( 2 ones, base: 18 ) 19 is prime.
( 7 ones, base: 14 ) 8108731 is prime.
( 19 ones, base: 2 ) 524287 is prime.
( 5 ones, base: 17 ) 88741 is prime.
( 3 ones, base: 20 ) 421 is prime.
( 7 ones, base: 17 ) 25646167 is prime.
( 3 ones, base: 21 ) 463 is prime.
( 2 ones, base: 22 ) 23 is prime.
( 3 ones, base: 24 ) 601 is prime.
( 5 ones, base: 22 ) 245411 is prime.
( 17 ones, base: 11 ) 50544702849929377 is prime.
( 11 ones, base: 17 ) 2141993519227 is prime.
( 5 ones, base: 23 ) 292561 is prime.
( 5 ones, base: 24 ) 346201 is prime.
( 19 ones, base: 10 ) 1111111111111111111 is prime.

/*
* Move right first, then diagonally down & to the left,
* then down, then diagonallyup & to the right. Repeat.
* Print primes in the order found.
*/
( 2 ones, base: 2 ) 3 is prime.
( 3 ones, base: 2 ) 7 is prime.
( 2 ones, base: 4 ) 5 is prime.
( 3 ones, base: 3 ) 13 is prime.
( 5 ones, base: 2 ) 31 is prime.
( 2 ones, base: 6 ) 7 is prime.
( 3 ones, base: 5 ) 31 is prime.
( 7 ones, base: 2 ) 127 is prime.
( 3 ones, base: 6 ) 43 is prime.
( 7 ones, base: 3 ) 1093 is prime.
( 3 ones, base: 8 ) 73 is prime.
( 2 ones, base: 10 ) 11 is prime.
( 5 ones, base: 7 ) 2801 is prime.
( 7 ones, base: 5 ) 19531 is prime.
( 7 ones, base: 6 ) 55987 is prime.
( 2 ones, base: 12 ) 13 is prime.
( 13 ones, base: 2 ) 8191 is prime.
( 3 ones, base: 12 ) 157 is prime.
( 11 ones, base: 5 ) 12207031 is prime.
( 13 ones, base: 3 ) 797161 is prime.
( 5 ones, base: 12 ) 22621 is prime.
( 3 ones, base: 14 ) 211 is prime.
( 2 ones, base: 16 ) 17 is prime.
( 3 ones, base: 15 ) 241 is prime.
( 5 ones, base: 13 ) 30941 is prime.
( 13 ones, base: 5 ) 305175781 is prime.
( 17 ones, base: 2 ) 131071 is prime.
( 2 ones, base: 18 ) 19 is prime.
( 3 ones, base: 17 ) 307 is prime.
( 7 ones, base: 13 ) 5229043 is prime.
( 13 ones, base: 7 ) 16148168401 is prime.
( 19 ones, base: 2 ) 524287 is prime.
( 7 ones, base: 14 ) 8108731 is prime.
( 5 ones, base: 17 ) 88741 is prime.
( 3 ones, base: 20 ) 421 is prime.
( 2 ones, base: 22 ) 23 is prime.
( 3 ones, base: 21 ) 463 is prime.
( 7 ones, base: 17 ) 25646167 is prime.
( 5 ones, base: 22 ) 245411 is prime.
( 3 ones, base: 24 ) 601 is prime.
( 5 ones, base: 23 ) 292561 is prime.
( 11 ones, base: 17 ) 2141993519227 is prime.
( 17 ones, base: 11 ) 50544702849929377 is prime.
( 19 ones, base: 10 ) 1111111111111111111 is prime.
( 5 ones, base: 24 ) 346201 is prime.


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#CantorOrderingRep1s051106
May_10_2006

I'm up to 4733 and there's still only 1 prime that can be expressed as
more than 1 non-trivial repunit... 31 (still 111_5 and 11111_2). All the
rest (bigger than 2) have 0 or 1 non-trivial repunit representations.

Here are all of the primes up to 4733 with non-trivial representations...
(trivial being 1 or 11)

7: 2
13: 2
31: 3
43: 2
73: 2
127: 2
157: 2
211: 2
241: 2
307: 2
421: 2
463: 2
601: 2
757: 2
1093: 2
1123: 2
1483: 2
1723: 2
2551: 2
2801: 2
2971: 2
3307: 2
3541: 2
3907: 2
4423: 2

Too many of the others to print.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeRep1Reps051006
May_07_2006

Update to:
http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AnotherSequence050706

Just had a thought. Add 2 to the previous sequence to include both base-1
and 1 base P for prime number P. AT&T doesn't have that one either.
Possible starts depending on how repunits are defined...


  • 0,1,1,2,1,2,1,1,1,1,3 - Base 2 and up, 2 digits or more.
  • 1,2,2,3,2,3,2,2,2,2,4 - Base 1 and up, 2 digits or more or base 2 and
    up, 1 digit or more.
  • 2,3,3,4,3,4,3,3,3,3,5 - Base 1 and up, 1 digit or more.


None of those are found in the online encyclopedia as of now.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#UpdatedSequence050706
May_07_2006

My poor little laptop is gonna blow up. It's running too many prime
number programs at once : ).

Here's another sequence... The number of ways to represent each prime as a
repunit in some base. Add 1 to each if you want to include base 1. AT&T
doesn't seem to have it with or without base 1. I'm surprised by the
small numbers. I was expecting to see some bigger counts. I'm down to
823 and haven't seen anything above 3 so far and I think I've only seen
that once, in base 31 (11111_2, 111_5 and 11_30). Not surprisingly, 1 is
by far the most common so far...

bash-3.1$ ./RepCount | head -40
2: 0
3: 1
5: 1
7: 2
11: 1
13: 2
17: 1
19: 1
23: 1
29: 1
31: 3
37: 1
41: 1
43: 2
47: 1
53: 1
59: 1
61: 1
67: 1
71: 1
73: 2
79: 1
83: 1
89: 1
97: 1
101: 1
103: 1
107: 1
109: 1
113: 1
127: 2
131: 1
137: 1
139: 1
149: 1
151: 1
157: 2
163: 1
167: 1
173: 1

Here's the code. Obviously there's room to stream-line it. About half
the cases I'm checking don't need to be checked I think.


#include "Integer.h"
#include
#include
#include "bconlib.h"

using namespace std;

int main ()
{
Integer base, numDigits, TestNum, rep1, rep1ct;

for ( TestNum = 2; ; TestNum++ )
{
if ( isprime (TestNum))
{
rep1ct = 0;
for ( base = 2; base < TestNum; base++ )
{
rep1 = 1;
for ( numDigits = 2; numDigits < TestNum; numDigits++ )
{
rep1 = rep1 * base + 1;
if ( rep1 == TestNum ) rep1ct++;
}
}
cout << TestNum << ": " << rep1ct << endl;
}
}
}


Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#AnotherSequence050706
May_07_2006

Repeating 1 primes in a graph up to 2-123 digits on the x-axis, base
2-1000 on the y-axis. Base 2 at the top, 1000 at the bottom. 2 digits on
the left, 123 on the right. '_' denotes a left or right margin. 'P'
indicates a prime. Needs to be viewed in fixed width font.

http://taz.cs.wcupa.edu/~spalmer/Rep1Graph.html

If this graph were extended infinitely, using the method from before, it
would include every prime (except 2_10) at least once, probably numerous
times for many I bet (every prime, P, is 11 in base P-1).
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeGraph050706
May_04_2006

#
# Number of digits in repunit primes
#
bash-3.1$ awk '{print $1}' PrimeRepUnits.txt | sed -e :a -e 'N;s/\n/,/g;ta'

2,3,3,2,3,5,2,3,5,7,7,7,7,3,2,11,2,3,5,5,7,13,13,13,13,3,7,3,2,3,5,7,11,17,17,2,19,19,19,19,19,19,3,11,17,3,11,17,2,5,5,23,3,5,19,7,3,2,5,17,5,29,2,5,11,7,17,31,31,31,31,3,13,2,13,3,7,2,5,7,19,23,29,3,41,2,5,13,43,43,43,5,31,19,2,7,19,47,47,47,19,3,5,2,11,31,41,53,53,3,17,41,47,7,3,17,2,41,3,13,59,2,7,11,53,7,37,61,61,3,5,17,47,5,19,29,2,3,7,19,19,67,5,7,3,61,2,29,59,3,31,41,71,71,71,71,71,2,7,13,5,7,73,73,5,3,19,47,73,41,3,5,37,2,3,5,79,3,7,2,23,31,41,5,83,17,5,19,11,43,7,17,2,61,3,7,43,47,71,89,3,19,7,5,13,37,7,2,17,37,97,97,13,47,3,5,37,47,2,3,101,101,2,59,19,103,103,97,3,19,2,17,107,107,107,107,2,17,109,109,109,109,109,3,5,13,3,2,79,107,23,37,113,29,43,73,89,7,59,3,5,19,31,5,3,19,5,5,7,67,43,2,7,37,59,5,23,31,127,127,127,127,127,127,7,5,17,109,2,37,3,31,131,47,71,13,5,37,2,11,19,137,2,3,61,139,139,79,3,23,3,5,5,31,7,83,3,17,19,37,2,7,13,17,149,149,149,149,149,2,3,13,29,127,151,151,151,3,5,3,61,2,7,17,107,157,157,157,7,79,109,13,89,7,17,151,3,37,2,3,5,7,43,163,163,163,163,163,3,5,19,101,5,53,109,2,137,3,19,167,167,167,3,1 7,23,79,2,5,11,37,47,3,173,173,173,173,5,167,3,151,5,31,2,19,2,7,43,17,19,157,18 1,181,181,167,7,47,37,3,59,3,17,2,13,89,157,17,191,2,3,7,5,193,3,11,73,2,31,47,1 97,2,5,199,37,3,7,31,5,19,61,3,7,13,17,5,7,37,3,59,2,41,211,211,11,137,191,3,73,3,13,107,7,19,47,7,13,29,139,2,5,151,223,223,223,223,11,2,127,5,227,227,2,11,29,3,2,113,61,89,97,7,19,53,227,3,197,7,2,7,67,5,109,239,2,109,227,17,31,241,241,24 1,19,3,3,37,17,41,197,5,2,127,7,13,17,89,227,251,251,19,5,19,79,5,151,2,23,59,25 7,257,11,31,5,13,109,149,239,31,37,2,197,5,19,263,263,263,7,13,5,241,3,7,113,13,251,2,11,19,29,47,269,269,2,241,41,79,97,271,271,271,271,271,271,3,11,53,37,5,17,5,23,2,31,5,19,109,3,47,3,47,2,7,281,2,7,13,29,31,283,283,283,5,37,53,13,3,23,3,5,47,283,3,7,13,163,2,5,3,31,293,7,59,269,17,23,73,41,17,53,113,7,193,37,101,7,19,173,5,67,179,2,53,307,307,5,3,2,43,311,2,109,173,313,313,313,3,67,17,19,23,67,2,41,307,157,317,317,317,317,317,11,13,149,7,31,37,227,283,31,5,17,67,3,2,79,24 1,331,331,3,19,43,67,101,79,113,17,73,197,2,3,61,5,19,337,337,337,157,277,11,97,5,7,3,109,3,23,103,2,67,337,347,347,347,347,2,3,7,17,107,349,349,7,227,3,17,2,5,7,353,353,353,353,79,211,307,11,13,17,137,3,2,5,59,101,359,359,199,7,13,197,17,1 51,11,17,2,11,19,239,367,17,173,3,5,19,19,2,67,5,13,23,373,373,71,283,43,2,3,73,17,31,379,3,7,53,2,13,67,3,17,199,307,383,383,383,383,383,383,83,31,71,101,2,31,197,293,11,19,389,389,11,79,3,103,317,5,3,7,2,5,13,3,11,13,29,7,19,2,127,199,401,401,401,3,13,71,167,383,3,7,19,283,3,7,337,13,31,2,5,13,43,409,17,389,13,31,157,3,5,11,139,3,53,191,5,7,2,5,7,17,347,419,419,2,61,97,71,97,103,109,17,19,61,173,3,67,157,359,127,151,181,97,101,53,97,2,41,389,17,19,431,2,37,41,433,433,3,3,71,257,7,13,17,89,5,2,7,17,43,5,41,47,151,439,439,439,67,2,13,23,199,47,37,109,19,281,3,7,2,5,43,19,167,449,449,449,449,449,7,29,59,389,3,71,167,3,61,2,3,101,163,5,43,457,457,457,5,257,2,29,7,31,59,307,461,461,461,461,2,31,313,397,463,463,7,7 1,97,2,7,17,11,467,23,59,31,59,61,293,17,41,103,127,277,5,239,383,3,167,263,43,1 27,191,2,7,179,211,5,479,479,479,11,19,19,401,79,2,13,31,127,193,487,487,487,487,337,3,13,2,5,71,401,31,67,5,113,131,269,409,263,3,5,331,47,67,127,2,499,3,227,4 79,2,149,5,37,503,11,5,17,19,13,2,19,181,509,509,509,67,3,17,5,491,71,3,5,29,2,2 69,19,139,521,521,521,2,7,19,37,227,523,67,3,37,61,43,17,5,67,79,3,5,3,7,19,3,11,31,43,331,3,503,5,5,7,11,211,2,3,5,541,541,541,541,541,541,13,173,359,11,13,317,41,2,19,503,547,547,7,31,5,149,3,13,359,13,41,3,29,193,41,61,433,2,43,227,5,17,557,317,73,541,3,7,79,61,2,379,5,37,263,563,563,101,239,79,3,67,73,3,5,11,19,131,2,5,31,569,569,2,17,167,181,571,571,571,571,3,5,337,19,2,109,139,227,577,577,57 7,577,521,3,5,47,139,311,349,19,211,3,13,31,167,7,47,3,7,103,13,127,2,43,137,179,271,29,47,587,7,131,2,11,13,113,83,131,197,593,593,5,191,41,17,2,7,17,599,599,5 99,599,599,2,337,233,3,13,5,503,3,2,229,281,607,61,3,7,23,157,13,7,563,2,3,31,43,131,613,613,613,613,13,17,2,89,349,5,101,103,313,317,617,617,2,31,181,251,281,5 21,11,619,619,619,619,487,3,7,19,271,53,3,127,271,3,11,61,29,397,29,2,199,631,63 1,103,13,23,3,617,5,17,193,277,59,67,31,353,2,113,613,2,3,151,13,541,643,643,3,1 27,613,5,13,199,461,2,7,19,23,7,647,5,73,349,19,461,541,2,463,17,43,59,211,653,1 1,7,17,113,7,2,257,29,409,659,659,2,7,73,151,223,661,661,661,5,383,569,23,41,173,191,43,181,631,37,347,587,61,83,3,139,137,3,23,181,227,2,547,19,193,673,673,673,61,617,449,467,2,3,41,107,677,127,5,37,7,2,41,683,683,127,3,29,127,17,83,227,13,199,241,2,43,691,43,107,5,157,3,31,101,151,379,7,5,29,191,2,7,107,167,3,701,701,701,701,701,101,499,101,397,31,137,2,13,17,71,11,17,37,43,257,709,709,709,7,23,59,191

#
# Base 10 values of first 200 repunit primes (ordered as described # yesterday)
bash-3.1$ head -200 PrimeRepUnits.txt | awk '{print $2}' | sed -e :a -e 'N;s/\n /,/g;ta'

3,13,7,5,31,31,7,43,2801,127,1093,19531,55987,73,11,12207031,13,157,22621,
30941,5229043,8191,797161,305175781,16148168401,211,8108731,241,17,307,88741,
25646167,2141993519227,131071,50544702849929377,19,109912203092239643840221,
524287,1111111111111111111,6115909044841454629,29043636306420266077,
459715689149916492091,421,10778947368421,689852631578947368421,463,
17513875027111,1502097124754084594737,23,245411,292561,11111111111111111111111,
601,346201,7282588256957615350925401,321272407,757,29,637421,
148020807352107352204781,732541,7369130657357778596659,31,837931,
610851724137931,917087137,751670559138758105956097,
568972471024107865287021434301977158534824481,2147483647,
26063080998214179685167270877966651,243270318891483838103593381595151809701,
1123,2458736461986831391,37,6765811783780036261,1483,3092313043,41,2625641,
4201025641,70481514601025641025641025641,180432677378625641025641025641025641,
739052246542850625641025641025641025641025641,1723,
7538867501749984216983927242653776257689563451,43,3500201,40911050578149780601,
26656068987980386414408582952871386493955339704241,
35842614220783025524408588074144786493150233831596714503,
279199061472649689615930789290784389297167871396904357110743,3835261,
20585646725737777436116973149348140195500598968701,
585578449280908796570517800071,47,9684836827,869333244926326187979597262939,
177635683940025046467781066894531,423622795798733187216959754496018087627393990881167960767,70169234660105574400577005075855017842743056666917902427141,
1868467947605686541562499217713,2551,6377551,53,178250690949465223,
5451909197716512648567801549394409749475252856973123,
953470608251114628059528312260750980775135610852327164630237682734201,
615840114784814774501200690134862345946783236130283731411280186824640601,
94800483779652702112291995272136379042013221035884653418370569190962917425415732643821,2971,7141212583461249612878870081,4192533190739557589316560117434014038636743222283527117084573816370081,
116052004561246271601363039971898739754708554056434805985460385542224954675745081,31401724537,3307,12638179502096199521694978001,59,35048777985489339918082908475322279372162192908009414029627686016258551,
3541,1809873235795386729241,155306613932666028670208812450645212905178047040045530562317564121001023821,
61,47446779661,614910264406779661,295913145648117012032064667285782778591891525423728813559322033898305084745762711864406779661,52379047267,
19013087418896543607659206142267856546797091624826498592389251997,2305843009213693951,56065687629692436349945381294682921858769274981456436532996640647681369599401,
3907,15018571,48453916488902607769120106731,
28647027924883365832009197540551494206203337922266156117533489001511682209161111787,
16007041,435686197988821897112429141998291,586553146232068395470571577233998687006533145904541,
67,4423,83925549247,573352114691143033129973591044159,751410597400064602523400427092397,
56436777630861204610228497995848224493886299348863214641450495790307809339190661333386939668397177299125252187,
21700501,100343116693,4831,217413056830109525893225879971494401116211707207353652378688651472683845527821169829480608663693240736432822901,
71,4666530080888666270779140579710144927536231884057971,105180509469901317872088653758222878213754560007453623188405797101449275362318840579710144927536231884057971,
5113,34987327501952148741715973931001901034456358966279363081,113892272217800388917563305886676849934477281231425494342533202719055481441,
3754733257489862401973357979128773,3546245297457217493590449191748546458005595187661976371,
143798195172461138521036839345269251740737334259640879028155379795667047030720519999127,
4298038738591350241903359894361937263902417766066948735111854394786520954312466554848504069671001,
61097003103184669235517359417485905028897850322027200141703138362247062800773927423870139498763891657761796267,
73,141276239497,19681767848550770169481,28792661,153436090543,1051153199500053598403188407217590190707671147285551702341089650185945215953,
5111329463430071646630167819950683399621676569261698373582346123709742512021745954241,
30397351,5701,5713895385466654457755990930505701,181404334391011050943780483249696498285394414616499641295459892913837589927621789880701,
1023859838465486686363016033998704522272171328793086532353874352382193497640442165979330173110543821617750919555161286749549814172693201,
1730995823890967242587808530196681934696717844461757939646025856921040336541,6007,
35615581,83050688872181792062911510280689447476301196161748956451938490287421,79,6163,39449441,
536009503964613991286957683005287140685493324523698332668846831791767500295593367113600925667991227216067,6481,
265462278481,83,1285978139266094478723147821625123656873807,2628720457810922675790147629853783693934858456227291510607,
36131245185867635814784593015648683957307663236864868592149169629717865084751,
48037081,1815516149411504925816848838815851358994487656027133573770941622975018443816715265278378295348087618707241356050904372886003491785803,
6218272796370530483675222621221,52822061,54285057541336632875522658938453311,
22390512687494871811,
1794793457558728068881896380589101991122424128407905197767108407160765177758155523,
438668366137,10897549321353520105257105986881,89,471980165848307086289091737864067345661144228405301030029496596510943367487295952103442941824530468373935096268264601,
8011,502628805631,7573342771994130615522569017449106969771683171811814657814243611224093474194720211,
475168497376063793664595366231925074732194660541461281907913805888132377764452416406845831,
28987302297978853232099574652437415613020972905970153030166957882349456201761876270617872053290431240588599728184946817952685377877484351,
618970019642690137449562111
Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#Rep1DigitSeq050406
May_03_2006

Here's a fun one AT&T doesn't seem to have yet. Modelled after Cantor's
diagonalization. All primes of the form 111...111 (repunits, some might
say) in some base.

In (numdigit,base) pairs, the numbers are checked in the following order.

2 digits, base 2
2 digits, base 3
3 digits, base 3
3 digits, base 2
2 digits, base 4
3 digits, base 4
4 digits, base 4
4 digits, base 3
4 digits, base 2
2 digits, base 5
...
...
...

In that fashion, all repunits in all bases will eventually be checked for
primacy.

If just the primes are printed, the sequences below appear (Hope I copied
and pasted right. If not, it's easy enough to reproduce.) All three
columns are infinite sequences. I imagine only the first and second
columns might be "interesting".


Number of value_base_10 base where
ones it's a repunit
2 3 2
3 13 3
3 7 2
2 5 4
3 31 5
5 31 2
2 7 6
3 43 6
5 2801 7
7 127 2
7 1093 3
7 19531 5
7 55987 6
3 73 8
2 11 10
11 12207031 5
2 13 12
3 157 12
5 22621 12
5 30941 13
7 5229043 13
13 8191 2
13 797161 3
13 305175781 5
13 16148168401 7
3 211 14
7 8108731 14
3 241 15
2 17 16
3 307 17
5 88741 17
7 25646167 17
11 2141993519227 17
17 131071 2
17 50544702849929377 11
2 19 18
19 109912203092239643840221 19
19 524287 2
19 1111111111111111111 10
19 6115909044841454629 11
19 29043636306420266077 12
19 459715689149916492091 14
3 421 20
11 10778947368421 20
17 689852631578947368421 20
3 463 21
11 17513875027111 21
17 1502097124754084594737 21
2 23 22
5 245411 22
5 292561 23
23 11111111111111111111111 10
3 601 24
5 346201 24
19 7282588256957615350925401 24
7 321272407 26
3 757 27
2 29 28
5 637421 28
17 148020807352107352204781 28
2 3 2
3 13 3
3 7 2
2 5 4
3 31 5
5 31 2
2 7 6
3 43 6
5 2801 7
7 127 2
7 1093 3
7 19531 5
7 55987 6
3 73 8
2 11 10
11 12207031 5
2 13 12
3 157 12
5 22621 12
5 30941 13
7 5229043 13
13 8191 2
13 797161 3
13 305175781 5
13 16148168401 7
3 211 14
7 8108731 14
3 241 15
2 17 16
3 307 17
5 88741 17
7 25646167 17
11 2141993519227 17
17 131071 2
17 50544702849929377 11
2 19 18
19 109912203092239643840221 19
19 524287 2
19 1111111111111111111 10
19 6115909044841454629 11
19 29043636306420266077 12
19 459715689149916492091 14
3 421 20
11 10778947368421 20
17 689852631578947368421 20
3 463 21
11 17513875027111 21
17 1502097124754084594737 21
2 23 22
5 245411 22
5 292561 23
23 11111111111111111111111 10
3 601 24
5 346201 24
19 7282588256957615350925401 24
7 321272407 26
3 757 27
2 29 28
5 637421 28
17 148020807352107352204781 28


I think it's soo cool how that numDigit column is prime too. I was
thinking about that as a test for primacy today. So far I don't see it.
Alot of numbers can be ruled out that way, but so far it seems that we
could rule numbers out until the end of time without ever ruling one in.

And the code, I guess...

#include "Integer.h" // needs -lgmpxx -lgmp
// Available: here
// http://www.frenchfries.net/paul/factoring/source.html
#include < iostream>
#include < math.h>
#include "bconlib.h"

using namespace std;

int main ()
{
short int i=1;
Integer lcv, thisprime=2, lastprime=2,gap,oldgap,maxgap, numDigits,
base, Ival, IPower;

for ( base=2; ; base++ )
{
for ( numDigits=2 ; numDigits<=base; numDigits++ )
{
Ival = 1;
IPower = 1;
for ( lcv = 1; lcv < numDigits; lcv++ )
{
IPower *= base;
Ival += IPower;
}
if ( isprime (Ival) )
{
cout << numDigits << "\t\t" << Ival << "\t\t"
<< base << endl;
if ( !isprime (numDigits))
cerr << endl << numDigits << " is not prime." << endl;
}
}
numDigits--;
for ( Integer base2=2; base2<=base-1 ; base2++ )
{
Ival = 1;
IPower = 1;
for ( lcv = 1; lcv < numDigits; lcv++ )
{
IPower *= base2;
Ival += IPower;
}
if ( isprime (Ival) )
{
cout << numDigits << "\t\t" << Ival << "\t\t"
<< base2 << endl;
if ( !isprime (numDigits))
cerr << endl << numDigits << " is not prime." << endl;
}
}
}
}

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MorePrimes050306
May_02_2006

This is interesting. Up to some big number with lots of digits in each
base up to base 135 (so far... still running), if I find all primes of the
form 111...1 in the range in the base, the number digits in the primes are
also prime numbers.

In other words, if N is a prime in base b and it's of the form

b^(k-1) + b^(k-2) + ... + b^2 + b^1 + b^0

Then the number of digits, k, appears to be prime number. It's not
obvious to me why that is.

It is obvious why k can't be even. Alternating & repeating (10)'s
multiplied by 11 can give any even (111...111) result, so besides 11, any
number represented with an even number of 1's in some base can't be prime.
It's got 11 (in that base) as a factor. That's easy. I'm not seeing why
it can't be an odd, non-prime number of 1's though. Or maybe it can and I
just haven't stumbled across one like that yet.

Hmm. Let's look at the first non-prime odd numbers. 9 and 15...
111111111 (9 1's) is also 111 * 1001001. Doesn't matter what base I don't
think.

How 'bout 15?
111111111111111 = 15 = 5 x 3
so 111111111111111 / 111 = 1001001001001
or 111111111111111 / 11111 = 10000100001

You can see it easily if you do the long division by hand. I'm thinking
the number of digits does have to be a prime if the number will be prime.
It looks to me like if k has factors a & b, then numbers represented by
(a)1's and (b)1's are factors of the number represented by (k)1's which
would mean that the (k)1's number can't be prime.

I wonder if this fact might lead to a way to check for primacy... Prob'ly
not. I'll think about that for a while... Probably someone already knows
all this anyway. Still fun exploring.

Here are some of the numbers I've found so far.
/*
* Number of digits in prime numbers represented by 111....1 in some base.
* AT&T has some of these up 'til 15 or so. Not the higher ones. I'm not
* gonna bother for now. Maybe some other time. They have bigger
* computers than I do anyway. ;-)
*
* For example, the first number in base 7 is 5. This means...
* 11111_7 is prime. Let's check.
* 7^4 + 7^3 + 7^2 + 7 + 1 = 2401 + 343 + 49 + 7 + 1 = 2801.
* That's prime... here on this list...
* http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_1000_prime_numbers
*
*/
Base 2
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423,
Base 3
3, 7, 13, 71, 103, 541, 1091, 1367, 1627,
Base 4
2,
Base 5
3, 7, 11, 13, 47, 127, 149, 181, 619, 929,
Base 6
2, 3, 7, 29, 71, 127, 271, 509, 1049,
Base 7
5, 13, 131, 149, 1699,
Base 8
3,
Base 9

Base 10
2, 19, 23, 317, 1031,
Base 11
17, 19, 73, 139, 907,
Base 12
2, 3, 5, 19, 97, 109, 317, 353, 701,
Base 13
5, 7, 137, 283, 883, 991, 1021, 1193,
Base 14
3, 7, 19, 31, 41,
Base 15
3, 43, 73, 487,
Base 16
2,
Base 17
3, 5, 7, 11, 47, 71, 419,
Base 18
2,
Base 19
19, 31, 47, 59, 61, 107, 337, 1061,
Base 20
3, 11, 17,
Base 21
3, 11, 17, 43, 271,
Base 22
2, 5, 79, 101, 359, 857,
Base 23
5,
Base 24
3, 5, 19, 53, 71, 653, 661,
Base 25

Base 26
7, 43, 347,
Base 27
3,
Base 28
2, 5, 17, 457,
Base 29
5, 151,
Base 30
2, 5, 11, 163, 569,
Base 31
7, 17, 31,
Base 32

Base 33
3, 197,
Base 34
13,
Base 35
313,
Base 36
2,
Base 37
13, 71, 181, 251, 463, 521,
Base 38
3, 7, 401, 449,
Base 39
349, 631,
Base 40
2, 5, 7, 19, 23, 29, 541, 751,
Base 41
3, 83, 269, 409,
Base 42
2,
Base 43
5, 13,
Base 44
5, 31, 167,
Base 45
19, 53, 167,
Base 46
2, 7, 19, 67, 211, 433,
Base 47
127,
Base 48
19, 269, 349, 383,
Base 49

Base 50
3, 5, 127, 139, 347, 661,
Base 51

Base 52
2, 103, 257,
Base 53
11, 31, 41,
Base 54
3, 389,
Base 55
17, 41, 47, 151, 839,
Base 56
7, 157,
Base 57
3, 17, 109, 151, 211, 661,
Base 58
2, 41,
Base 59
3, 13, 479,
Base 60
2, 7, 11, 53, 173,
Base 61
7, 37, 107, 769,
Base 62
3, 5, 17, 47, 163, 173, 757,
Base 63
5,
Base 64

Base 65
19, 29, 631,
Base 66
2, 3, 7, 19,
Base 67
19, 367,
Base 68
5, 7, 107, 149,
Base 69
3, 61,
Base 70
2, 29, 59, 541, 761, 1013,
Base 71
3, 31, 41, 157,
Base 72
2, 7, 13, 109, 227,
Base 73
5, 7,
Base 74
5, 191,
Base 75
3, 19, 47, 73, 739,
Base 76
41, 157, 439, 593,
Base 77
3, 5, 37,
Base 78
2, 3, 101, 257,
Base 79
5, 109, 149, 659,
Base 80
3, 7,
Base 81

Base 82
2, 23, 31, 41,
Base 83
5,
Base 84
17,
Base 85
5, 19,
Base 86
11, 43, 113, 509,
Base 87
7, 17,
Base 88
2, 61, 577,

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#MorePrimes050206
Apr_26_2006

And here's the sequence I submitted to AT&T...
(http://www.research.att.com/~njas/sequences/index.html) From the last
column of the output below.

1, 2, 4, 6, 8, 14, 18, 20, 22, 34, 36, 44, 52, 72, 86, 96, 112, 114, 118,
132, 148, 154, 180, 210, 220, 222

Ouch! I'm an idiot. Now AT&T has it. I managed to miss that earlier too
somehow. Oops. Now they've got it twice. Don't know how I managed to
typo two of these.

Anyway, this one is the running value for the maximum gap between prime
numbers as the value of the prime gets bigger. Don't know why. This is
pure speculation, but I think some of these might be interesting to look
at as radices. One of these intervals is 6. For base 6, all primes
(above 6) end in 1 or 5. I wonder if choosing a radix from any of these
other intervals might have any interesting properties for representation
of prime numbers.

My laptop's getting hot. CPU must be working. :-). Oh. I didn't find
the next prime number with all 1's during dinner. No surprise there, huh?

==
bash-3.00$ ./PrimeGap
3 - 2 Gap: 1 Max Gap: 1
5 - 3 Gap: 2 Max Gap: 2
11 - 7 Gap: 4 Max Gap: 4
29 - 23 Gap: 6 Max Gap: 6
97 - 89 Gap: 8 Max Gap: 8
127 - 113 Gap: 14 Max Gap: 14
541 - 523 Gap: 18 Max Gap: 18
907 - 887 Gap: 20 Max Gap: 20
1151 - 1129 Gap: 22 Max Gap: 22
1361 - 1327 Gap: 34 Max Gap: 34
9587 - 9551 Gap: 36 Max Gap: 36
15727 - 15683 Gap: 44 Max Gap: 44
19661 - 19609 Gap: 52 Max Gap: 52
31469 - 31397 Gap: 72 Max Gap: 72
156007 - 155921 Gap: 86 Max Gap: 86
360749 - 360653 Gap: 96 Max Gap: 96
370373 - 370261 Gap: 112 Max Gap: 112
492227 - 492113 Gap: 114 Max Gap: 114
1349651 - 1349533 Gap: 118 Max Gap: 118
1357333 - 1357201 Gap: 132 Max Gap: 132
2010881 - 2010733 Gap: 148 Max Gap: 148
4652507 - 4652353 Gap: 154 Max Gap: 154
17051887 - 17051707 Gap: 180 Max Gap: 180
20831533 - 20831323 Gap: 210 Max Gap: 210
47326913 - 47326693 Gap: 220 Max Gap: 220
122164969 - 122164747 Gap: 222 Max Gap: 222

== And here's some code...
#include "Integer.h" // needs -lgmpxx -lgmp
// Available: here
// http://www.frenchfries.net/paul/factoring/source.html
#include
#include

using namespace std;

int main ()
{
short int i=1;
Integer lcv, thisprime=2, lastprime=2,gap,oldgap,maxgap, numDigits=0;
lcv = 3;
for ( ; ; )
{
if ( isprime (lcv) )
{
lastprime = thisprime;
thisprime = lcv;
gap = thisprime - lastprime;
maxgap = max (gap, maxgap);
if ( oldgap < gap )
{
cout << thisprime << " - " << lastprime
<< " Gap: " << gap << " Max Gap: "
<< maxgap << endl;
oldgap = gap;
}
}
lcv += 2;
}
}

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeGaps042606
Apr_26_2006

2,19,23,317,1031.... Maybe I'll let this run during supper. Wonder what
the next number is? AT&T's encyclopedia of integer sequences doesn't have
it. Oh yes they do. I had a typo... Next comes 49081, but that term is
listed as a "probable prime" as is the next one at 86453 1's. I don't
think my little laptop is gonna find either of them.

http://www.research.att.com/~njas/sequences/?q=2%2C19%2C23%2C317%2C1031&sort=0&fmt=0&language=english&go=Search

The number of digits in prime numbers made up just of 1's (base 10). I
wonder if the digit counts will all be prime? The two from AT&T's site
are prime too. I suppose this must also be a countably infinite set.
The numbers got big fast.

I submitted another one to AT&T earlier. I'll post that later.

==
1 - not prime
11 - prime
111 - not prime
1111 - not prime
...
1111111111111111111 - prime
... 11111111111111111111111 - prime
...

==
x = 1
for (;;)
x = 10x + 1

==
Those are the numbers I mean...

Here's some code...

#include "Integer.h" // Needs libgmpxx and libgmp
#include
#include

using namespace std;

int main ()
{
Integer lcv, thisprime=1, lastprime,gap,oldgap,maxgap, numDigits=0;
for ( lcv = 1; ; lcv = lcv * 10 + 1 ) {
numDigits++;
if ( isprime (lcv) )
{
lastprime = thisprime;
thisprime = lcv;
gap = thisprime - lastprime;
maxgap = max (gap, maxgap);
cout << numDigits << endl << endl;
/*
if ( oldgap < gap )
{
cout << thisprime << " - " << lastprime
<< " Gap: " << gap << " Max Gap: "
<< maxgap << endl;
oldgap = gap;
}
*/
}
}
}

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#PrimeOnes042606
Apr_20_2006

http://www.pen.k12.va.us/Div/Winchester/jhhs/math/quotes.html

293 "We must say that there are as many squares as there are numbers."
-- Galileo Galilei

Wow! An observation of countable infinity from Galileo. Must've been a
couple hundred years before Cantor, I think. Very surprising... to me at
least.

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#GalileoCountableInf042006
Mar_02_2006

Math quotes:
http://www.geocities.com/capecanaveral/hangar/7773/quotes.html

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#QuotesMarch0206
Jan_14_2006

Mathematics in the mainstream press. I wonder if mathematicians will be
more important or if computers will have replaced mathematicians by the
time our kids are adults. Computers have already replaced computers...

http://www.businessweek.com/magazine/content/06_04/b3968001.htm

Link for this entry: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#BusinessWeek-011406