mathematics

Nov_26_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Horner25Nov07 That code has now been updated. Base conversion using the experimental method is working (to some degree.... Testing has been cursory.). So far, the experimental method does not compare favorably with Horner's method. I still need to clean up and optomize, but I've got no reason to think that's going to make up the difference. An applet and source files are here: http://home.ccil.org/~remlaps/WebConvert/ I haven't tried any, but negative bases probably aren't working. Update: Parallel processing still needs to be explored. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#WebConvert26Nov07

Nov_25_2007 http://home.ccil.org/~remlaps/WebConvert/ This will eventually be a side by side comparison enabling use of either Horner's method for base conversion or the experimental base conversion shown here--- http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DiagConver13Sep07 So far, only the Horner's method part is implemented. Big plus for Horner's method... It's way way way easier to implement Horner's method. It only took 1/2 hour or so and very little thought once the GUI and the interface were done. I've already spent longer than that fighting writer's block on the experimental method. It's not easy to visualize how to structure it programatically to avoid repeating the div/mod functions. It wouldn't be bad to just implement it moving remainders rightwards and quotients downwards, I want to save the result of the div/mod from one pass so I can use it again later. That complicates it. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Horner25Nov07

Nov_25_2007 Here's the table from http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DiagConver13Sep07 Reoriented. Thinking about array indexing... 3 7 1 0 7 10/31 0/30 = 0;30 (7+30)10/31 =370/31 =11;29 (29+1)10/31 =300/31 =9;21 (21+0)10/31 =210/31 =6;24 (24+7) =31 =1;0 0 10/31 0;0 110/31 =3;17 (17+9)10/31 =260/31 =8;12 (12+6) =18 +1 (carry) 19 10/31 0;0 30/31 =0;30 (30+8) =1;7 7 10/31 0;0 0 + 1 (carry) 1 10/31 0 0 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#ReOrient25Nov07

Oct_24_2007 Updating the java code I posted a while back as follows... lastv=new BigInteger("1"); gap=new BigInteger("3"); mult=new BigInteger("1"); for (int lcv=0;lcv<1000;lcv+=1) { if (lastv.isProbablePrime(100)) { System.out.println (lcv + ": f(" + lcv + ")= " + lastv + " : " + gap + "p"); pcount++; } else { ccount++; System.out.println (lcv + ": f(" + lcv + ")= " + lastv + " : " + gap + "c"); } lastv = lastv.add(gap); gap = gap.multiply(mult); gap = gap.add(BigInteger.ONE); // gap = gap.pow(Integer.valueOf(mult.toString())); } Start with 1,4 and change the gap by adding 1 to it. It gives 218 primes out of 1,000 and 840 out of 5,000. It's apparently A034856 "C(n + 1, 2) + n - 1" http://www.research.att.com/~njas/sequences/A034856 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#UpdateSequence24Oct07

Oct_17_2007 http://spreadsheets.google.com/ccc?key=pk6AtB0QfKvo3_4yFgEX7UQ&hl=en&pli=1 f(x) = 9^x + 1 2,10,82,730,6562,... As with 4^x + 1 yesterday, it looks like there are primes that can/can't be factors... Based on repeating cycles in yesterday's spread sheet, for 9^x+1, so far I've got {2,5,17,29,41,53,73,97...}. I can rule out {3,7,11,13,19,23, 31,37,61,67,...}. Can't tell about {43,47,59,79,83,89 or 101}. 9x+2 looks interesting too. It gives 6 primes in the first 10. Possible factors include: {3,11,17,43,59,83}, can't be factors include: {2,5,7,13,19,23,29,37,41,61,67,73}, Unknown: {31,47,53,61,67,79,89,97,101}. To switch between 9x+1 and 9x+2, just switch cell B4. 2 for 9x+1, 3 for 9x+2. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NinePowers17Oct07

Oct_17_2007 The gap/offset method for generating 4^n+1 generates lots of other functions too. My favorite so far... 2 + ((9^n)+1)/2 /* * Main.java * * * To change this template, choose Tools | Template Manager * and open the template in the editor. */ package simpleplaywithnumbers; import java.math.BigInteger; /** * * @author remlaps */ public class Main { /** Creates a new instance of Main */ public Main() { } /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here BigInteger lastv, gap, mult; /** * {2,3,4} == 2^(2n)+1 == 4^n + 1 * {2,3,2} == 3*2^n-1 * {3,2,2} == 2^(n+1) + 1 * {2,3,3} == (3^(n+1) + 1)/2 * {2,2,3} == 3^n+1 * {2,2,2} == 2^(n+1) * {2,2,4} == Number of distinct quadratic residues mod 4^n * (A039301: whatever that means) * {2,3,1} == 3^n + 2 * {2,2,1} == 2*(n+1) * {3,2,1} == 2*(n+1) + 1 * {2,1,2} == 2^n + 1 * {3,1,3} == {3,4,7,16,43,124,367,1096,3283,9844,...} * {3,2,3} == {3,5,11,29,83,245,731,2189,6563,19685,...} == 3^n+2 * {3,2,9} == 2 + ((9^n)+1)/2 * {5,7,3} == {5,12,33,96,285,852,2553,7656,22965,68892,...} */ lastv=new BigInteger("3"); gap=new BigInteger("4"); mult=new BigInteger("9"); for (int lcv=0;lcv<10;lcv++) { if (lastv.isProbablePrime(100)) { System.out.println (lcv + ": f(" + lcv + ")= " + lastv + " : " + gap + "p"); }else { System.out.println (lcv + ": f(" + lcv + ")= " + lastv + " : " + gap + "c"); } lastv = lastv.add(gap); gap = gap.multiply(mult); } } } Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MorePlay16Oct07

Oct_17_2007 http://spreadsheets.google.com/ccc?key=pk6AtB0QfKvo3_4yFgEX7UQ&hl=en# Looks like {5,13,17,29,37,41,53,61,...} are primes which can be factors of 4^n+1. That sequence also begins: Pythagorean primes: primes of form 4n+1. http://www.research.att.com/~njas/sequences/A002144 Also Fermat numbers mod 340 are all 257. 0+257 192(340)+257 12632256(340)+257 = 65793(192)(340)+257 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FermPrimeFactors16Oct07

Oct_17_2007 All fermat numbers are 17 mod 80 and 2 mod 85? All but 2 are 65 mod 192? --- See the "Copy of 4^x + 1" tab. --- http://spreadsheets.google.com/ccc?key=pk6AtB0QfKvo3_4yFgEX7UQ&hl=en# In columns that have zeros, it appears that wherever the first 0 appears dictates the length of the cycle. 0 in f(5) means a cycle of 10. 0 in f(16) gives cycle of 32. So, it looks like every f(2^n) has to have a unique factor. The cycle of length 16 starting at f(8) will never land on another power of 2. Same with the length 32 cycle starting at f(16). So mod 0 entries are not going to be able to sieve out additional primes. Looking at the PrimeMods tab, I think some primes will not be factors of any fermat numbers (or any of the 4^n-1 values) 2,3,7,11,19,31,43,47, ... can't tell about 59, 67, 71,... I don't have enough numbers calculated to know whether 59, 67 and 71 go into a non-zero cycle or eventually land on 0. AT&T has {2,3,7,11,19,31,43,47,59} as the start of series: Primes of the form x^2 + y^2 + 2. However, I have 73 in my list of non-factors. That's not in their list. http://www.research.att.com/~njas/sequences/A079739 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FermatAgain15Oct07

Oct_15_2007 F(15) = 1073741825 = 2^(2^15)+1 F(16) = 4294967297 = 2^(2^16)+1 F(17) = 17179869185 = 2^(2^17)+1 I'm wondering if we can use the fact that F(15) + 2^14*3 = F(16) F(16) + 2^15*3 = F(17) and F(15) & F(17) are multiples of 5. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MoreFermNum15Oct07

Oct_15_2007 Here's another way to list the fermat numbers... #include <iostream> #include "Integer.h" using namespace std; int main() { Integer lastv, gap=3; for (lastv=2;lastv < 10000000;gap=gap*4) { cout << lastv << ", "; lastv = lastv + gap; } cout << lastv << endl; } Looking at it this way, then looking at mods, we see 1.) Mod 5 alternates {0,2,0,2,...} so {f(3),f(5),f(7),...} cannot be prime. 2.) Mod 17 goes {5,0,14,2,5,0,14,2,...} so {f(6), f(10), f(14),... cannot be prime.} 3.) Mod 67 rules out some odds again. Don't care. 4.) Mod 257 goes {0,254,242,194,2,5,17,65,0,254,...} so {f(12), f(20), f(28), ...} cannot be prime. 5.) Skipping 1025. Should be odd again. 6.) Mod 4097 rules out {f(6), f(18), f(24), ..} 7.) Skipping 16385. Some odds again. Don't care. 8.) Mod 65537 rules out {f(8), f(24), f(40),...} 9.) Mod (f(10)) rules out {f(10), f(30), f(50),...} 10.) In general, mod(f(x)) has it's first 0 at x and goes in cycles of 2(x). That's about all I can manage in a spread sheet, so let's see what kind of sieve is started... f(x) 0 - prime 1 - prime 2 - prime 3 - m(5) 4 - prime 5 - m(5) 6 - m(17),m(4097) 7 - m(5) 8 - prime 9 - m(5) 10 - m(17),m(1048577) 11 - m(5) 12 - m(257) 13 - m(5) 14 - m(17) 15 - m(5) 16 - 641 * 6700417 17 - m(5) 18 - m(17),m(4097),m(f(18)) 19 - m(5) 20 - m(257) 21 - m(5) 22 - m(17) 23 - m(5) 24 - m(65537) 25 - m(5) 26 - m(17) 27 - m(5) 28 - m(257) 29 - m(5) 30 - m(17),m(4097) 31 - m(5) 32 - 274177 * 67280421310721 33 - m(5) 34 - m(17) 35 - m(5) 36 - m(257),m(f(12)) 37 - m(5) 38 - m(17) 39 - m(5) 40 - m(65537) 41 - m(5) 42 - m(17),m(f(14)),m(4097) 43 - m(5) 44 - m(257) 45 - m(5) 46 - m(17) 47 - m(5) 48 - m(f(16) 49 - m(5) 50 - m(17),m(1048577) 51 - m(5) 52 - m(257) 53 - m(5) 54 - m(17),m(4097),m(f(18)) 55 - m(5) 56 - m(65537) 57 - m(5) 58 - m(17) 59 - m(5) 60 - m(257),m(f(20)) 61 - m(5) 62 - m(17) 63 - m(5) ... Here's a spread sheet showing the last_value + offset calculations and the modulous table. http://spreadsheets.google.com/pub?key=pk6AtB0QfKvo3_4yFgEX7UQ 16 & 32 were problematic, but I'm wondering if we can sieve out the rest now. That's gonna have to be it for today, but maybe I'll program the sieve some time. Update: Looks like I got the formula for fermat numbers wrong... Should be 2^(2^x)+1. I think I did 2^(2x)+1. This sieve might still be right, if the fermat numbers are a subset of the ones I looked at. I'm thinking they might be. lol... Just like Nature & the AP... Wrong but accurate. ; -) Difference is, now I know I have to start over when I get time. The disadvantage of squeezing this stuff into my spare time. I don't have time to figure it out now though. Update 2: A hurried sieve implementation leaves f(1),f(2), f(4), f(8), etc.. unfilled. I guess those are probably the fermat numbers. Looks unpromising. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Fermat15Oct07

Oct_14_2007 Cases where +/- offset are both primes. ;;; f(x)=1^(2x) +/- 0 C:\Personal\PROGRA~1\cpp>myfun 100 1 2 0 ;;; f(x)=2^(2x) +/- 1 C:\Personal\PROGRA~1\cpp>myfun 100 2 2 1 1: 5, 3 ;;; f(x)=3^(2x) +/- 2 C:\Personal\PROGRA~1\cpp>myfun 100 3 2 2 1: 11, 7 2: 83, 79 ;;; f(x)=4^(2x) +/- 3 C:\Personal\PROGRA~1\cpp>myfun 100 4 2 3 1: 19, 13 3: 4099, 4093 ;;; f(x)=5^(2x) +/- 4 C:\Personal\PROGRA~1\cpp>myfun 100 5 2 4 ;;; f(x)=6^2(x) +/- 5 C:\Personal\PROGRA~1\cpp>myfun 100 6 2 5 1: 41, 31 2: 1301, 1291 ;;; f(x)=7^2x +/- 6 C:\Personal\PROGRA~1\cpp>myfun 100 7 2 6 ;;; f(x)=8^2x +/- 7 C:\Personal\PROGRA~1\cpp>myfun 100 8 2 7 ;;; f(x)=9^2x +/- 8 C:\Personal\PROGRA~1\cpp>myfun 100 9 2 8 1: 89, 73 2: 6569, 6553 5: 3486784409, 3486784393 ;;; f(x)=10^2x +/- 9 C:\Personal\PROGRA~1\cpp>myfun 100 10 2 9 ;;; f(x)=11^2x +/- 10 C:\Personal\PROGRA~1\cpp>myfun 100 11 2 10 ;;; f(x)=12^2x +/- 11 C:\Personal\PROGRA~1\cpp>myfun 100 12 2 11 ;;; f(x)=13^2x +/- 12 C:\Personal\PROGRA~1\cpp>myfun 100 13 2 12 1: 181, 157 2: 28573, 28549 ;;; f(x)=14^2x +/- 13 C:\Personal\PROGRA~1\cpp>myfun 100 14 2 13 ;;; f(x)=15^2x +/- 14 C:\Personal\PROGRA~1\cpp>myfun 100 15 2 14 1: 239, 211 ;;; f(x)=16^2x +/- 15 C:\Personal\PROGRA~1\cpp>myfun 100 16 2 15 1: 271, 241 2: 65551, 65521 ;;; f(x)=17^2x +/- 16 C:\Personal\PROGRA~1\cpp>myfun 100 17 2 16 ;;; f(x)=18^2x +/- 17 C:\Personal\PROGRA~1\cpp>myfun 100 18 2 17 3: 34012241, 34012207 ;;; f(x)=19^2x +/- 18 C:\Personal\PROGRA~1\cpp>myfun 100 19 2 18 ;;; f(x)=9^2x +/- 8 (up to 1000) C:\Personal\PROGRA~1\cpp>myfun 1000 9 2 8 1: 89, 73 2: 6569, 6553 5: 3486784409, 3486784393 ;;; f(x) = 1^1x +/- 0 C:\Personal\PROGRA~1\cpp>myfun 100 1 1 0 ;;; f(x) = 2^2x +/- 1 C:\Personal\PROGRA~1\cpp>myfun 100 2 2 1 1: 5, 3 ;;; f(x) = 3^3x +/- 2 C:\Personal\PROGRA~1\cpp>myfun 100 3 3 2 ;;; f(x) = 4^4x +/- 3 C:\Personal\PROGRA~1\cpp>myfun 100 4 4 3 ;;; f(x) = 5^5x +/- 4 C:\Personal\PROGRA~1\cpp>myfun 100 5 5 4 ;;; f(x) = 6^6x +/- 5 C:\Personal\PROGRA~1\cpp>myfun 100 6 6 5 ;;; f(x) = 7^7x +/- 6 C:\Personal\PROGRA~1\cpp>myfun 100 7 7 6 ;;; f(x) = 8^8x +/- 7 C:\Personal\PROGRA~1\cpp>myfun 100 8 8 7 ;;; f(x) = 9^9x +/- 8 C:\Personal\PROGRA~1\cpp>myfun 100 9 9 8 ;;; f(x) = 10^10x +/- 9 C:\Personal\PROGRA~1\cpp>myfun 100 10 10 9 C:\Personal\PROGRA~1\cpp> Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Counting14Oct07

Oct_14_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MyFun.cpp14Oct07 I modified the program to work with any function of the form f(x)=prime ^ (exp * x) + offset. http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Afunction14Oct07 I started looking at f(x)=3^(2*x) + 2 after seeing an e-mail about the fermat primes. The program below will look at fermat primes or 9^x+2 based on command line arguments... Fermat primes: (f(x)=2^(2x)+1) || 4^x+1 C:\Personal\PROGRA~1\cpp>myfun 10 2 2 1 0: 2, 0 1: 5, 3 2: 17, 15 4: 257, 255 8: 65537, 65535 f(x)=3^(2x)+2 || 9^x+2 C:\Personal\PROGRA~1\cpp>myfun 10 3 2 2 0: 3, -1 1: 11, 7 2: 83, 79 4: 6563, 6559 5: 59051, 59047 7: 4782971, 4782967 f(x)=5^(2x)+4 || 25^x+4 C:\Personal\PROGRA~1\cpp>myfun 10 5 2 4 0: 5, -3 1: 29, 21 3: 15629, 15621 5: 9765629, 9765621 f(x)=7^(2x)+6 || 49^x+6 C:\Personal\PROGRA~1\cpp>myfun 10 7 2 6 0: 7, -5 8: 33232930569607, 33232930569595 #include <iostream> #include "Integer.h" using namespace std; Integer f(int, int, int, int); Integer pow (Integer, int); Integer pow (Integer n, int p) { Integer Iret=1; for (int lcv=0; lcv < p; lcv++ ) Iret=Iret*n; return Iret; } Integer f(int x, int pv, int ex, int o) { Integer Iret; Iret = pow(pv,(ex * x))+o; return Iret; } int main(int argc, char*argv[]) { int lcv, max, offset, pv, expon; Integer Iv1, Iv2; if (argc != 5) { cerr << "Usage:\n\t" << argv[0] << " [max] [prime_val] [exponent] [offset]" << endl; exit(-1); } max=atoi(argv[1]); pv=atoi(argv[2]); expon=atoi(argv[3]); offset=atoi(argv[4]); for (lcv=0;lcv < max;lcv++) { Iv1=f(lcv,pv,expon,offset); Iv2=Iv1-(2 * offset); // if ( ( isprime (Iv1) || isprime (Iv2) ) && Iv2 > 0 ) // if ( isprime (Iv1) && isprime (Iv2) && Iv2 > 0 ) if (isprime (Iv1)) cout << lcv << ": " << Iv1 << ", " << Iv2 << endl; } } Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Modifiedprog14Oct07

Oct_14_2007 /* * 9^n + 8, 9^n - 8 */ C:\Personal\PROGRA~1\cpp>myfun 100 8 myfun 100 8 2: 89, 73 4: 6569, 6553 7: 4782977, 4782961 10: 3486784409, 3486784393 /* * 9^n + 10, 9^n - 10 */ C:\Personal\PROGRA~1\cpp>myfun 100 10 myfun 100 10 3: 739, 719 4: 6571, 6551 9: 387420499, 387420479 18: 150094635296999131, 150094635296999111 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#OtherOffset14Oct07

Oct_14_2007 Are there only two pairs of numbers such that [3^(2*x)+2,3^(2*x)-2] are both prime? #include <iostream> #include "Integer.h" using namespace std; Integer f(int); Integer pow (Integer, int); Integer pow (Integer n, int p) { Integer Iret=1; for (int lcv=0; lcv < p; lcv++ ) Iret=Iret*n; return Iret; } Integer f(int x) { Integer Iret; Iret = pow(3,(2 * x))+2; return Iret; } int main(int argc, char*argv[]) { int lcv, max; Integer Iv1, Iv2; max=atoi(argv[1]); for (lcv=0;lcv < max;lcv++) { Iv1=f(lcv); Iv2=Iv1-4; if ( isprime (Iv1) && isprime (Iv2)) cout << lcv << ": " << Iv1 << ", " << Iv2 << endl; } } #### Sample Output #### C:\Personal\PROGRA~1\cpp>myfun 10 1: 11, 7 2: 83, 79 C:\Personal\PROGRA~1\cpp>myfun 100 1: 11, 7 2: 83, 79 C:\Personal\PROGRA~1\cpp>myfun 10000 1: 11, 7 2: 83, 79 Note1: 3^2*n == 9^n Note2: There are at least 3 pairs such that (9^n+2,9^n-10) are prime. C:\Personal\programming\cpp>myfun 10000 2: 83, 71 4: 6563, 6551 18: 150094635296999123, 150094635296999111 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MyFun.cpp14Oct07

Oct_14_2007 f(x) = 3^(2x)+2: 3,11,83,731,6563 is not found in AT&T's online encyclopedia of integer sequences. Neither is 3,11,83,6563 (first four primes). >(defun f (x) (+ (expt 3 (* 2 x)) 2)) F >(f 0) 3 ;;; prime >(f 1) 11 ;;; prime >(f 2) 83 ;;; prime >(f 3) 731 >(f 4) 6563 ;;; prime >(f 5) 59051 ;;; prime >(f 6) 531443 >(f 7) 4782971 ;;; Prime >(f 8) 43046723 >(f 9) 387420491 - fun f(x)=(pow(3,toInt (2* x)) + 2); val f = fn : int -> int - f(0); val it = 3 : int (* Prime *) - f(1); val it = 11 : int (* Prime *) - f(2); val it = 83 : int (* Prime *) - f(3); val it = 731 : int - f(4); val it = 6563 : int (* Prime *) - f(5); val it = 59051 : int (* Prime *) - f(6); val it = 531443 : int - f(7); val it = 4782971 : int (* Prime *) - f(8); val it = 43046723 : int - f(9); val it = 387420491 : int - f(10); val it = 3486784403 : int - f(11); val it = 31381059611 : int - f(12); val it = 282429536483 : int (* Prime *) - f(13); val it = 2541865828331 : int (* Prime *) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Afunction14Oct07

Sep_29_2007 I put the USHCN triangle up in google docs... Just playing around. http://docs.google.com/Doc?id=dgb2ngdw_1f34336 I also notice that this could also be considered 2 triangles. 1 1,2 1,3,4 1,4,7,8 1,5,11,15,16 ... And its mirror. Unlike Pascal's triangle, the right-most value in each row is calculated by adding 1 to the entry to its left. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#USHCNtriangleOnGoogle29Sep07

Sep_29_2007 Again back to the USHCN triangle... http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Pisot28Sep07 There seem to be a couple series that make turns from diagonals to veriticals. That's sort of odd. I guess it has to do with when the vertical passes the "middle" value in the row. The value that gets repeated. The column is one series above the turn and a second series below... (or something like that, if that makes any sense) A000125 - 1,2,4,8,15,26,42,... 1,2,4,8 from the diagonal, then veritical for 15,26,42,... (I speculate for the ... part) A000127 - 1,2,4,8,16,31,57,... 1,2,4,8 from the diagonal starting at the right on top, then 16,31,57,... from the veritcal Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#USHCNSeries29Sep07

Sep_29_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Pisot28Sep07 AT&T doesn't find the sequence [11, 1221, 134431, ...] either. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DoubleMiddlePascal29Sep07

Sep_28_2007 Sure wish I had time to look at this stuff more carefully. I noticed the number 1221 at climateaudit.org. That's the number of stations in the US Historical Climate Network's database. It reminded me of Pascal's triangle, but it's not quite right. It's got an extra 2. I wondered what would happen if we built a whole triangle like that? All values calculated as in Pascal's triangle, but the middle digit is always repeated. 1 1 1 2 2 1 1 3 4 4 3 1 1 4 7 8 8 7 4 1 1 5 11 15 16 16 15 11 5 1 1 6 16 26 31 32 32 31 26 16 6 1 1 7 22 42 57 63 64 64 63 57 42 22 7 1 1 8 29 64 99 120 127 128 128 127 120 99 64 29 8 1 So I searched AT&T for 1,1,1,2,2,1,1,3,4,4,3,1. It's not found. So I summed the rows. 1 1 - 2 1 2 2 1 - 6 1 3 4 4 3 1 - 16 1 4 7 8 8 7 4 1 - 40 1 5 11 15 16 16 15 11 5 1 - 96 1 6 16 26 31 32 32 31 26 16 6 1 - 224 1 7 22 42 57 63 64 64 63 57 42 22 7 1 - 512 1 8 29 64 99 120 127 128 128 127 120 99 64 29 8 1 - 1152 1 9 37 93 163 219 247 255 256 256 255 247 219 163 93 37 9 1 - 2560 Then, I searched for the sums and found A057711... Number of states in the planning domain FERRY, when n-3 cars are at one of two shores while the (n-2)nd car may be on the ferry or at one of the shores. http://www.research.att.com/~njas/sequences/A057711 That series starts with 0,1,2,6, but the two seem to run together from 2 onwards. Then, I calculated some more sums and they matched AT&T's prediction. As usual, nothing proven, but a potentially interesting observation. I searched for the 2560 row in AT&T and found nothing. (1,9,37,93,...) Column 3 is A000124, Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts. http://www.research.att.com/~njas/sequences/A000124 Column 4 starts like A000125 but it veers off in row 6. http://www.research.att.com/~njas/sequences/A000125 It's hard to fish the diagonals out like this. I'll have to double check later when I have more time, but some of them are found. Not suprisingly, one diagonal gives powers of 2. The one below it gives powers of 2 minus 1. The next one down gives Eulerian numbers 2^n - n - 1. http://www.research.att.com/~njas/sequences/A000295 After that, 2^n - 1 - n(n+1)/2. http://www.research.att.com/~njas/sequences/A002662 After that 2^n - C(n,0)- ... - C(n,3). http://www.research.att.com/~njas/sequences/A002663 Then, 2^n - C(n,0)- ... - C(n,4). http://www.research.att.com/~njas/sequences/A002664 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Pisot28Sep07

Sep_23_2007 I'm up to 9725 and the top prime count is still 1794, with 13. There were a bunch of new 10's though. There have been no zero's since 4334. 1090 of them up until then. I'm a little surprised by the way it's behaving. It's acting the same way the palindromes did when I looked at them a couple years ago. Larger numbers seem to lead to higher counts, not lower. I'm also surprised that 0 counts seemed pretty common until 4334, then they just disappeared. Very strange. Or maybe I've got another programming problem. The change happens at the change in data files. That's suspicious. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PatPrimes23Sep07

Sep_20_2007 I found a memory leak in my program the other day and had to fix it and restart at 4335. No new maximum counts since then. There's another run of 4 consecutive primes at 4344 with suffix of 11. 434411 is prime, so is 4344434411. 43444344434411 is not, so the run of 4 was somewhere further along in the list. There are 1090 with 0 primes so far (out of 6869). Out to 400 repetitions, from 1 to 6869, the top 10 prime generators are: 2397+11 9 1512+11 9 1383+11 9 5168+11 10 4344+11 10 3654+11 10 1266+11 10 87+11 10 3969+11 11 1794+11 13 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MorePatternPrimes20Sep07

Sep_16_2007 Down to 1979, here are the top 20 primes generated by appending a suffix to a repeating pattern (out to 400 repetitions). Don't know why I decided to program this. Just thought it might be fun. It's been swamping my poor little laptop for about a day now. i.e. the top count, 1794 generates 13 primes of the from 179411 or 1794179411 or 17941794179411... out to 400 repetitions of the 1794. Surprisingly, there are 603 patterns so far don't that don't generate any primes at all. For example, in the set {194311, 1943194311, 19431943194311, ... } out to 400x1943, there are no prime numbers. (All assuming my slapped together program is doing what I think it is) The first column is the repeating pattern, +11 means append 11 to the repeating pattern. Second column is the number of primes found out to 400 pattern repetitions. $ sort +2 -3n +0 -1nr patprime.txt | tail -20 | awk '{print $1" "$3}' 729+11 7 276+11 7 61+11 7 59+11 7 34+11 7 16+11 7 10+11 7 1775+11 8 ;;; example --- 177517751775177511 1653+11 8 1557+11 8 1260+11 8 861+11 8 78+11 8 27+11 8 17+11 8 1512+11 9 1383+11 9 1266+11 10 87+11 10 1794+11 13 The longest run of consecutive primes so far was 4, for the pattern 1404. Don't know what they are yet. I'm kind of thinking the 0's might be more interesting than the ones with counts. Not sure what I'll look at next, if anything. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PatternPrimes16Sep07

Sep_15_2007 2, 3, 2, 2, 5, 2, 3, 7, 2, 2, 2, 3, 3, 2, 5, 11, 2, 2, 3, 13,... http://www.research.att.com/~njas/sequences/?q=10%2C11%2C10%2C10%2C101%2C10%2C11%2C111%2C10%2C10%2C10%2C11%2C11%2C10%2C101%2C1011%2C10%2C10%2C11&sort=0&fmt=0&language=english&go=Search If I did it right, here's the same series in binary. AT&T doesn't have that one. 10,11,10,10,101,10,11,111,10,10,10,11,11,10,101,1011,10,10,11,1101,... Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#CountingPrimeFactors15Sep07

Sep_13_2007 Incidentally, here's an example of a diagonal-wise conversion built upon the factor check described at- http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Factors2-13Sep07 3 7 1 0 7 10/31 10(3)/31 = 30/31 = 0;30 10/31 0;0 10(7+30)/31=370/31 = 11;29 10/31 0;0 10(0+11)/31 = 110/31 = 3;17 10(29+1)/31 = 300/31 = 9;21 10/31 0;0 10(0+3)/31 = 30/31 = 0;30 10(17+9)/31 = 260/31 = 8;12 10(21+0)/31 = 210/31 = 6;24 0 + 1(carry) (30 + 8) = 38 = 1;7 12 + 6 = 18 + 1(carry) 24+7 = 31 = 1;0 1 7 19 0 >(+ (* 1 (expt 31 3)) (* 7 (expt 31 2)) (* 19 (expt 31 1)) (* 0 (expt 31 0))) 37107 So as expected, diagonal conversion does seem to work. I also performed normalization as I went. That seems preferable to the column-wise aproach. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DiagConver13Sep07

Sep_13_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Factor13Sep07 Not quite, but close I think. We also need to mod the last digit by the base. 31 is a factor of 37107. By completing 1 diagonal, we get 31 in the ones place for base 31. After carrying, that'll be 0. For N digits, we'll need (N-1) small divisions instead of 1 big one. 3 7 1 0 7 10/31 10(3)/31 = 30/31 = 0;30 10/31 10(7+30)/31=370/31 = 11;29 10/31 10(29+1)/31 = 300/31 = 9;21 10/31 10(21+0)/31 = 210/31 = 6;24 24+7 = 31 31 % 31 = 0 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Factors2-13Sep07

Sep_13_2007 I thought about this on the way home tonight, since (I think) we can do these base conversions from right to left or left to right... Maybe the diagonal method will work for factoring? Run as if converting from base 10 to the number you want to know whether it's a factor. If the last digit in a base is not a 0, the base is not a factor. This one tests to see if 29 is a factor of 47319. It's not. We don't need to complete the base conversion. We just need the first diagonal. Seems to me like it should work. Since the last digit is a 20 (K), 29 is not a factor of 47319. Next up, one which is a factor... 4 7 3 1 9 10/29 40/29 = 1;11 10/29 10(11 + 7)/29 = 180/29 = 6;6 10/29 10(6+3)/29 = 90/29 = 3;3 10/29 10(3+1)/29 = 40/29 = 1;11 11+9 = 20 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Factor13Sep07

Sep_13_2007 I'm thinking maybe it'll be better to go diagonally then column-wise. This is because going diagonally it might be possible to merge and normalize during the same pass. Going column-wise, merging could be done during the same pass, but normalization would require a second pass. Basically, I think going diagonally would fill the results polynomial from right to left. Going column-wise fills it left to right. Colums might be preferred if maybe synthetic division be done from left to right in lieu of normalizing? That would be cool, but I'm not optomistic. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Tactics13Sep07

Sep_12_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#OneCellFunction12Sep07 Here's the fillCell function in C++ instead of SML/NJ, along with some code to drive it. #include <iostream> using namespace std; class cell{ private: int quot; int rem; public: void fillCell (const int dalrem, const int aquot, const int inbase, const int outbase) { quot = ((dalrem + aquot) * inbase) / outbase; rem = ((dalrem + aquot) * inbase) % outbase; } void printCell() { cout << quot << ", " << rem << endl; } }; int main() { cell OneCell; int dalrem, aquot, inbase, outbase; cout << "Enter [dalrem] [aquot] [inbase] [outbase] => "; cin >> dalrem >> aquot >> inbase >> outbase; OneCell.fillCell(dalrem, aquot, inbase, outbase); OneCell.printCell(); } c:\Personal\programming\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 0 1 12 14 0, 12 C:\Personal\PROGRA~1\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 10 13 12 14 19, 10 C:\Personal\PROGRA~1\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 12 9 12 14 18, 0 C:\Personal\PROGRA~1\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 4 17 12 14 18, 0 === Let's try a simple conversion using C++ fillCell Say 314 base 5 to base... ummm... 17 # # Implied 0, 3 from 1st digit # C:\Personal\PROGRA~1\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 0 3 5 17 0, 15 Column 1 0,15 --- # # 15 from column 1 quotient, 1 from 2nd digit # C:\Personal\PROGRA~1\cpp>rbcon Enter [dalrem] [aquot] [inbase] [outbase] => 15 1 5 17 4, 12 Column 1 & 2 [0,15] [---] [----] [4,12] # # 12 from column 2 remainder # 4 from 3rd digit # Combine 0,4,12+4 0,4,16 Here's the verification... (+ (* 3 (expt 5 2)) (* 1 (expt 5 1)) (* 4 (expt 5 0))) 84 (+ (* 4 (expt 17 1)) (* 16 (expt 17 0))) 84 So as expected, we find that 314_5 goes to 4G_17. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#OneCellCPP12Sep07

Sep_12_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SixDigitCon10Sep07 If we consider the digits in the original numeral as (quotient, remainder) couples where the remainders are each silent 0s, here's an SML/NJ function to fill any cell in the conversion (prior to digit normalization)... (* * dalrem = remainder from cell diagonally above and leftwards. * aquot = quotient from cell above. * inbase = base converting from. * outbase = base convering to. *) fun fillCell ( dalrem, aquot, inbase, outbase ) = (((dalrem + aquot) * inbase) div outbase, ((dalrem + aquot) * inbase) mod outbase); And here are some examples which match the cells in the table they were drawn from. - fillCell (10, 13, 12, 14); (* Row 5, column 4 *) val it = (19,10) : int * int - fillCell (12, 9, 12, 14); (* Row 2, column 2 *) val it = (18,0) : int * int - fillCell (0, 1, 12, 14); (* Row 3, column 3 *) val it = (0,12) : int * int - fillCell (4, 17, 12, 14); (* Row 4, column 2 *) val it = (18,0) : int * int Note that this implies the existence of another possible notation system. Not one I can imagine any use for, but possible anyway... (q_n,r_n) X^n + (q_n-1, r_n-1) X^n-1 + ... + (q_2,r_2) X^2 + (q_1,r_1) X + (q_0,r_0) q-s are quotients, r's are remainders. I'm not quite sure what that means, but that's just an aside, so I'll note it and forget it. To perform the conversion, I think fillCell could be applied in either of two fashions... 1.) Column 1 top to bottom Column 2 top to bottom Column 3 top to bottom ... Column N-1 top to bottom Where column 1 is below the digit in the highest power of X and column N is in the ones place. -OR- 2.) Diagonal 1 top-left to bottom right Diagonal 2 top-left to bottom right Diagonal 3 top-left to bottom right ... Diagonal N-1 top-left to bottom right Once all of the cells are filled, an equivalent polynomial is built by adding dalrem + aquot in each cell. No multiplication or division. [technically, probably multiply by (inbase/outbase)^0] i.e. fun fillCell1 ( dalrem, aquot ) = dalrem + aquot; The resulting polynomial would then be normalized into a numeral, as before... Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#OneCellFunction12Sep07

Sep_10_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SixDigitCon10Sep07 It probably dosn't matter, but I was thinking these conversions could also be done diagonal-wise instead of column-wise. Top-left to bottom-right. Working from the longest diagonal in to the shortest. There might be some benefit from parallelizing the diagonals, but threads might wind up waiting for each other since information needs to pass down the diagonals. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Ordering10Sep07

Sep_10_2007 Here's a six digit conversion from 891472_12 to 40A4AA_14 with digit normalization. Very cool now that I know what to do with the remainder (and when). 8 9 1 4 7 2 12/14 96/14 = 6;12 12/14 72/14 = 5;2 12(9+12)/14 = 252/14 = 18;0 12/14 60/14 = 4;4 12(18+2)/14 = 240/14 = 17;2 12(0+1) = 12/14 = 0;12 12/14 48/14 = 3;6 12(4+17)/14 = 252/14 = 18;0 12(2+0)/14 = 14/14 = 1;10 12(4+12)/14 = 192/14 = 13;10 12/14 36/14 = 2;8 12(6+18)/14 = 288/14 = 20;8 12(0+1)/14 = 12/14 = 0;12 12(10+13)/14 = 276/14 = 19;10 12(10+7)/14 = 204/14 = 14;8 Normalize 2 28 8 31 24 10 2 28 8 32 10 10 2 28 10 4 10 10 4 0 10 4 10 10 4 0 A 4 A A Here's the verification... >(+ (* 2 (expt 14 5)) (* 28 (expt 14 4)) (* 8 (expt 14 3)) (* 31 (expt 14 2)) (* 24 (expt 14 1)) (* 10 (expt 14 0))) 2179670 >(+ (* 8 (expt 12 5)) (* 9 (expt 12 4)) (* 1 (expt 12 3)) (* 4 (expt 12 2)) (* 7 (expt 12 1)) (* 2 (expt 12 0))) 2179670 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SixDigitCon10Sep07

Sep_10_2007 Here's a five digit conversion in table form, with digit normalization. I think I'm finally starting to see what it is that I'm doing... The conversion proceeds column-wise top to bottom, left to right. Remainder from leftward column gets added to quotient in the current column. (Quotient goes down vertically, remainder goes down/right diagonally) 4 7 1 7 8 9/11 36/11 = 3;3 9/11 3(9)/11 = 27/11 = 2;5 9(7+3)/11 = 90/11 = 8;2 9/11 9(2)/11 = 18/11 = 1;7 9(8+5)/11 = 117/11 = 10;7 9(1+2)/11 = 27/11 = 2;5 9/11 9(1)/11 = 0;9 9(10+7)/11 = 153/11 = 13;10 9(2+7)/11 = 81/11 = 7;4 9(7+5)/11 = 108/11 = 9;9 Normalize 0 9+13 = 22 10 + 7 = 17 4 + 9 = 13 9 + 8 = 17 0 22 17 14 6 0 22 18 3 6 0 23 7 3 6 2 1 7 3 6 Here's a verification of the conversion... [20]> (+ (* 4 (expt 9 4)) (* 7 (expt 9 3)) (* 1 (expt 9 2)) (* 7 (expt 9 1)) (* 8 (expt 9 0))) 31499 [21]> (+ (* 2 (expt 11 4)) (* 1 (expt 11 3)) (* 7 (expt 11 2)) (* 3 (expt 11 1)) (* 6 (expt 11 0))) 31499 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FiveDigitConvert10Sep07

Sep_09_2007 Making progress on the scrolling problem I think. Might've replaced it with a first-entry problem though. Testing. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Cosmetics09Sep07

Sep_09_2007 Here's another example, going from 2112 base 3 to 125 base 7. Sorry I still haven't figured out the scrolling problem. 2 1 1 2 3/7 (2*3)/7 = 0;6 3/7 ((1+6)*3)/7 = 21/7 = 3;0 3/7 (3*3)/7 = 1;2 (1)*3/7 = 3/7 = 0;3 2 1 2 5 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#B3toB7Ex09Sep07

Sep_09_2007 This table is a beginning at organizing just how the recursive base conversion works. The table gets filled in top-left to bottom-right. I can't figure out how to get rid of the whitespace. Seems like it's being inserted by the script that creates the HTML page out of the individual files. It shows 3241_11 converted to BG5_19. Basically, you're filling out the lower-left triangle and moving the remainders around. It seems like remainders move diagonally down and to the right. I guess number of operations in general, for N digits will be: (N-1) + (N-2) + ... + 2 + 1 =?= N(N-1)/2 (I forget that identity... something like that) No digit normalization is necessary in this example. Now Scroll down... 3 2 4 1 11/19 33/19 = 1;14 11/19 11/19 = 0;11 176/19 = 9;5 11/19 220/19 = 11;11 99/19 = 5;4 11 16 5 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#BConExTab09Sep07

Sep_01_2007 This gnuplot code generates some interesting looking graphs. Polynomials made from the base 2 representations of primes. Substituting X for powers of 2.... # Output settings and destination # set terminal pdf set output 'PrimesT2.pdf' # Where to put the legend set key left top Right set title "Functions from primes in binary" f2(x) = 2 * x f3(x) = 3 * x + 1 f5(x) = x**2 + 1 f7(x) = x**2 + x + 1 f11(x) = x**3 + x + 1 f13(x) = x**3 + x**2 + 1 f17(x) = x**4 + 1 f19(x) = x**4 + x + 1 f23(x) = x**4 + x**2 + x + 1 f29(x) = x**4 + x**3 + x**2 + 1 f31(x) = x**4 + x**3 + x**2 + x + 1 f37(x) = x**5 + x**2 + 1 f41(x) = x**5 + x**3 + 1 f43(x) = x**5 + x**3 + x + 1 f47(x) = x**5 + x**3 + x**2 + x + 1 f53(x) = x**5 + x**4 + x**2 + 1 f59(x) = x**5 + x**4 + x**3 + x + 1 f61(x) = x**5 + x**4 + x**3 + x**2 + 1 plot [-1:1] f2(x),f3(x),f5(x),f7(x),f11(x),f13(x),f17(x),f19(x),f23(x),f29(x),f31(x),f37(x),f41(x),f43(x),f47(x),f53(x),f59(x),f61(x) plot [-10:10] f2(x),f3(x),f5(x),f7(x),f11(x),f13(x),f17(x),f19(x),f23(x),f29(x),f31(x),f37(x),f41(x),f43(x),f47(x),f53(x),f59(x),f61(x) plot [-100:100] f2(x),f3(x),f5(x),f7(x),f11(x),f13(x),f17(x),f19(x),f23(x),f29(x),f31(x),f37(x),f41(x),f43(x),f47(x),f53(x),f59(x),f61(x) plot [-1000:1000] f2(x),f3(x),f5(x),f7(x),f11(x),f13(x),f17(x),f19(x),f23(x),f29(x),f31(x),f37(x),f41(x),f43(x),f47(x),f53(x),f59(x),f61(x) plot [-10000:10000] f2(x),f3(x),f5(x),f7(x),f11(x),f13(x),f17(x),f19(x),f23(x),f29(x),f31(x),f37(x),f41(x),f43(x),f47(x),f53(x),f59(x),f61(x) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PrimeGraphs31Aug07

Aug_12_2007 Below is a start to a conversion algorithm for any number of digits. Of course I'm pausing now that I'm at the hard part. In the mean time, I noticed something. We can easily take advantage of the digit grouping base conversion method, for decimal anyway... I am thinking this might actually be useful. I can convert big numbers in 2 digit conversions, trading size of arithmetic for numbers of operations.. I don't think the remainder method can exploit this. Not sure. I'll have to think more about it later. Time for bed now. Examples with digit grouping: >(bcon '(87 94) 100 3) ;;; Base 100, Same as 8794_10 to 3 (1 1 0 0 0 1 2 0 1) >(bcon '(873 941) 1000 3) ;;; Base 1k, Same as 873941_10 to 3 (1 1 2 2 1 0 1 2 1 1 0 1 2) >(bcon '(9032 1023) 10000 3) ;;; Base 10k, Same as 90321023_10 to 3 (2 0 0 2 1 2 2 1 2 1 0 0 1 1 0 0 2) >(bcon '(91784 17502) 100000 3) ;;; 100k, Same as 9178417502_10 (2 1 2 2 0 0 1 2 2 2 1 0 2 2 0 2 1 0 2 2 2) >(bcon '(91784 17502) 100000 10) (9 1 7 8 4 1 7 5 0 2) >(bcon '(98917402 97356123) 100000000 3) ;;; 100m, Same as 9891740297356123_10 (1 2 1 0 0 0 1 0 1 1 2 0 2 0 1 0 2 0 0 2 2 1 1 1 2 2 0 2 0 0 1 1 1 1) Lisp Code: (defun bcon (L inBase outBase) (NormalL (congen L inBase outBase) outBase)) (defun congen (x inb outb) (cond ((equal x nil) nil) ((equal (rest x) nil) (first x)) ((equal (rest (rest x)) nil) (let ( (FD (floor (* (first x) inb) outb)) (irem (rem (* inb (first x)) outb)) ) (list FD (+ irem (first (rest x)))))) (* '(to be completed)) ) ) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#GeneralConvert12Aug07

Aug_12_2007 It's ugly, but here's a common lisp function for base conversion with 3 digits... Example: >(NormalL (con3 '(9 9 9) 90 2) 2) 1> (CON3 (9 9 9) 90 2) 2> (CONTWO (9 9) 90 2) <2 (CONTWO (405 9)) <1 (CON3 (18225 405 9)) (1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1) Code: (defun con3 (x inb outb) (let ( (FD (floor (* (first x) inb) outb)) (irem (mod (* inb (first x)) outb)) ) (cons (floor (* FD inb) outb) (let ((twodigs (contwo (cons (+ (first (rest x)) irem) (rest (rest x))) inb outb)) (irem2 (mod (* FD inb) outb))) (cons (+ (first twodigs) irem2) (rest twodigs)))))) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#ThreeDigits12Aug07

Aug_12_2007 Base conversion directly between bases without calculating powers of (in base/out base). normalL normalizes a list of coefficients for a base. contwo converts coefficients from input base to output base. Example: >(contwo '(15 11) 256 2) (1920 11) >(normalL (contwo '(15 11) 256 2) 2) (1 1 1 1 0 0 0 0 1 0 1 1) Code in lisp (tested using GCL, GNU Common Lisp) (defun contwo (x inb outb) (let ( (FD (floor (* (first x) inb) outb)) (irem (mod (* inb (first x)) outb)) ) (list FD (+ irem (first (rest x)))) )) (defun normalL (x b) (if (equal nil x) nil (if (equal (first x) 0) (normalL (rest x) b) (reverse (normList (reverse x) b 0))))) (defun normList (x b r) (if (null x) nil (if (equal (rest x) nil) ;;; One digit (let ( (idiv (floor (+ (first x) r) b)) (irem (rem (+ (first x) r) b)) ) (if (equal 0 idiv) (list irem) (cons irem (normList (list idiv) b 0))) ) ;;; Multiple digits (let ( (idiv (floor (+ (first x) r) b)) (irem (rem (+ (first x) r) b)) ) (cons irem (normList (rest x) b idiv)) ) ) ) ) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#TwoDigitConLisp12Aug07

Aug_12_2007 A lisp function for converting a 2 "digit" list to another 2 digit list. To get a digit, this would need to be followed by normalization. (defun contwo (x inb outb) (let ( (FD (floor (* (first x) inb) outb)) (irem (mod (* inb (first x)) outb)) ) (list FD (+ irem (first (rest x)))) )) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Sun_Aug_12_09:26:35_EDT_2007.25330

Aug_02_2007 Here's another conversion. Base 9 to base 14 this time. 3241_9 3,2,4,1 3(9/14),2,4,1 27/14,2,4,1 [1;13],2,4,1 1,15,2,4,1 1,[135/14],4,1 1,[9;9],4,1 9/14,[9;9],4,1 0;9,[9;9],4,1 0,18,13,1 0,162/14,13,1 0,162/14,117/14,1 0,[11;8],[8;5],1 0,11,16,6 0,12,2,6 0,C,2,6 C26 C26_14 I still don't know exactly what I'm doing, but I'm thinking we need rules according to the remaining power of (B1/B2) in the current position and rightward position. This isn't exactly right, but something like. 1.) If power_current > power_rightward, add current remainder to rightward coefficient. 2.) If power_current == power_rightward, perform division to the right and add the current remainder to the rightward divisor. 3.) If power_current < power_rightward, move right. 4.) Stay rightward until the power gets "low enough", then move back to the left and start over. I think backtracking will be required. That's painful. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#B9toB14FourDigits02Aug07

Aug_01_2007 A couple more base conversions... 2000_7 2,0,0,0 2(7/11)(7/11)(7/11),0,0,0 (14/11)(7/11)(7/11),0,0,0 [1;3](7/11)(7/11),0,0,0 1(7/11)(7/11),3(7/11)(7/11),0,0 [0;7],[1;10](7/11),0,0 0,8(7/11),10(7/11),0 0,56/11,10(7/11),0 0,5;1,10(7/11),0 0,[5;1],10(7/11),0 0,[5;1],(70/11),0 0,[5;1],[6;4],0 0,5,7,4 574_11 2111_7 2,1,1,1 2(7/11)(7/11)(7/11),1(7/11)(7/11),1(7/11),1 (14/11)(7/11)(7/11),1(7/11)(7/11),1(7/11),1 [1;3](7/11)(7/11),1(7/11)(7/11),1(7/11),1 1(7/11)(7/11),4(7/11)(7/11),1(7/11),1 (7/11)(7/11),4(7/11)(7/11),1(7/11),1 [0;7](7/11),4(7/11)(7/11),1(7/11),1 [0;7](7/11),(28/11)(7/11),1(7/11),1 [0;7](7/11),[2;6](7/11),1(7/11),1 0,9(7/11),7(7/11),1 0,(63/11),7(7/11),1 0,[5;8],7(7/11),1 0,[5;8],(49/11),1 0,[5;8],[4;5],1 0,5,12,6 0,6,1,6 616_11 6534 6,5,3,4 6(7/11)(7/11)(7/11),5(7/11)(7/11),3(7/11),4 (42/11)(7/11)(7/11),5(7/11)(7/11),3(7/11),4 [3;9](7/11)(7/11),5(7/11)(7/11),3(7/11),4 3(7/11)(7/11),14(7/11)(7/11),3(7/11),4 (21/11)(7/11),14(7/11)(7/11),3(7/11),4 [1;10](7/11),14(7/11)(7/11),3(7/11),4 [1;10](7/11),(98/11)(7/11),3(7/11),4 [1;10](7/11),[8;10](7/11),3(7/11),4 1(7/11),18(7/11),13(7/11),4 [0;7],126/11,13(7/11),4 [0;7],[11;5],(91/11),4 [0;7],[11;5],[8;3],4 0,18,13,7 0,19,2,7 1,8,2,7 1827_11 And one without the (7/11) clutter 5326_7 5,3,2,6 35/11,3,2,6 [3;2],3,2,6 3,5,2,6 21/11,5,2,6 1;10,5,2,6 1;10,35/11,2,6 1;10,3;2,2,6 1;10,3,4,6 1,13,4,6 7/11,13,4,6 0;7,13,4,6 0;7,91/11,4,6 0;7,8;3,4,6 0;7,8;3,28/11,6 0;7,8;3,2;6,6 0,15,5,12 0,15,6,1 1,4,6,1 1461_11 Compared to Horner's method... 5,3,2,6 35,3,2,6 38,2,6 === 38 * 7 = 266 266,2,6 268,6 === 268 * 7 = 1876 1876,6 1882 (divrem 1882 1331) (1 551) (divrem 551 121) (4 67) (divrem 67 11) (6 1) 1,4,6,1 So I think there are more steps in this method, but the arithmetic is smaller. Small enough to balance the number of steps? Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MoreFour01Aug07

Jul_31_2007 Here's a simple 4-digit conversion, one digit at a time... 1000_7 1,0,0,0 1(7/11)(7/11)(7/11),0,0,0 (7/11)(7/11)(7/11),0,0,0 [0;7](7/11)(7/11),0,0,0 0,7(7/11)(7/11),0,0 0,(49/11)(7/11),0,0 0,[4;5](7/11),0,0 0,4(7/11),5(7/11),0 0,28/11,35/11,0 0,[2;6],[3;2],0 0,2,9,2 292_11 And another, still simple... 1111_7 1,1,1,1 1(7/11)(7/11)(7/11),1(7/11)(7/11),1(7/11),1 (7/11)(7/11)(7/11),1(7/11)(7/11),1(7/11),1 [0;7](7/11)(7/11),1(7/11)(7/11),1(7/11),1 0,8(7/11)(7/11),1(7/11),1 0,(56/11)(7/11),1(7/11),1 0,[5;1](7/11),1(7/11),1 0,5(7/11),2(7/11),1 0,35/11,14/11,1 0,[3;2],[1;3],1 0,3,3,4 334_11 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SimpleFour31Jul07

Jul_31_2007 Well I've been thinking about it... That method is exactly Horner's method. 6453_7 is 2292_10. So there's nothing worth noticing there. I converted from base 7 to base 10, then from 10 to base 11. Already knew how to do that. I also moved away from the one digit at a time principle which I'd been trying to follow. Back to the drawing board. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FourDigsUpdate30Jul07

Jul_31_2007 Well I'm a moron. Here's a much easier way to look at it... It is almost exactly like Horner's method... Duh! 6543 going from base 7 to 11... 6,4,5,3 6(7/11) = 42/11 + 4/11 (46/11)(7/11) = 322/121 + 5/121 = 327/121 (327/121)(7/11) = (2289/1331) + (3/1331) = 2292/1331 [1;961] ### Div/Mod 2292/1331 1,[7;114] ### Div/Mod 961/121 1,7,[10;4] ### Div/Mod 114/11 1,7,10,4 17A4 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FourDigDirectCon31Jul07

Jul_30_2007 - pi; val it = 3.14159265359 : real - e; val it = 2.71828182846 : real Digits of pi interlaced with digits of e. 32.1741185298216852385496... Or absolute value when subtracted... 1.63731123513... Someone already logged the subtracted digits, not the interlaced ones. http://www.research.att.com/~njas/sequences/A073223 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#IrrationalPiE30Jul07

Jul_30_2007 Just for fun... Primes in base negative 10, up to 100. 2,3,5,7,191,193,197,199,183,189,171,177,161,163,167,153,159,141,147,131,133,139,123,129,117,... 0.2357191193197199183189171177161163167153159141147131133139123129117... It's wierd how some of those descending seeming numbers are ascending. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Neg10BasePrimes30Jul07

Jul_29_2007 Still not what I'm looking for... This is more or less the same thing as before. 6,5,4,3 base 7 to base 11 6(7/11)(7/11)(7/11), 5(7/11)(7/11), 4(7/11), 3 (42/11)(7/11)(7/11), 5(7/11)(7/11), 4(7/11),3 (294/121)(7/11), (35/11)(7/11), 4(7/11), 3 (2058/1331), (245/121), (28/11), 3 [1;727), (245/121), (28/11), 3 1, 972/121, 28/11, 3 1, 8;4, 28/11, 3 1, 8, 32/11, 3 1, 8, 2;10, 3 ## Terms converted, now normalize ## 1, 8, 2, 13 1, 8, 3, 2 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Another4Digits29Jul07

Jul_29_2007 Here's a 4 digit conversion without exploiting recursion. I'm still having trouble doing it recursively, but it's got to work. I must just be stupid. I keep losing track of where/when to carry the remainders doing it recursively. I note that doing it this way, I never need to carry remainders by more than one position... 3564 Base 7 to 17 3,5,6,4 (7/17)(7/17)(7/17),(7/17)(7/17),(7/17),1 3(7/17)(7/17)(7/17),5(7/17)(7/17),6(7/17),4 3(343/4913),5(49/289),6(7/17),4 1029/4913,245/289,42/17,4 0,1274/289,42/17,4 0,[4;118],42/17,4 0,4,160/17,4 0,4,[9;7],4 0,4,9,11 0,4,9,B 049B Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FourDigitConvert29Jul07

Jul_29_2007 This isn't easy. Here's a conversion from base 7 to base 17. I'm thinking it might like working on bases which are not relatively prime though. (i.e. 15 to 25 would use 3/5 instead of 15/25). 564 Base 7 to 17 5,6,4 (7/17)(7/17),(7/17),1 5(7/17)(7/17),6(7/17),4 (35/17)(7/17),6(7/17),4 [2;1](7/17),6(7/17),4 2(7/17),1(7/17) + 6(7/17),4 14/17,7(7/17),4 [0;14],7(7/17),4 0,14 + 49/17,4 0,[16;15],4 0,16,19 0,17,2 1,0,2 564_7 goes to 102_17 I haven't succeeded in doing one in 4 digits yet though. I keep confusing myself. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#GeneralBCON29Jul07

Jul_08_2007 Here's a silly question... I wonder what happens if you pass a musical melody through base conversion? In a simplistic representation, one octave might get a base 12 representation as follows... C : 0 C#/D_ : 1 D : 2 D#/E_ : 3 E : 4 F : 5 F# / G_ : 6 G : 7 G#/A_ : 8 A : 9 A#/B_ : A B : B A bit of mary had a little lamb, BAGABBB, would go B979BBB. Converted to base (-12), that would go to 1B038201B, which would get C#,B,C,D#,G#,D,C,C#,B Update: Which gets w,j,a,e,y,s,a,w,j at- http://www.frontiernet.net/~imaging/play_a_piano.html End-Update Can't tell what that would sound like now. I wonder if there are conversions that would preserve the "key" of the melody. (I think that's what it was called?) Of course, 1/8 notes, 1/4 notes, 1/2 notes, etc... create a representational challenge. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SongPascal08Jul07

Jul_07_2007 It seemed like this should work... Here's an example of a direct conversion from base 13 to base 17 applying a recursive method based on Horner's method... Showing more detailed arithmetic in my evaluation than I show in Horner's. Still I doubt if it's any faster than Horner's. Especially if normalization is necessary. No normalization was needed in this example. Maybe it never is, but I kind of doubt that. 476_13 to base 17 4,7,6 # Split out digits. (13/17)(13/17),(13/17),1 # List powers powers of ratio of bases. 4(13/17)(13/17),7(13/17),6 # Multiply digits by powers. (below) (52/17)(13/17),7(13/17),6 # Multiply first term by 13/17. [3;1](13/17),7(13/17),6 # Split out divisor/remainder. 3(13/17),(1*13/17)+(7*13/17),6 # Apply divisor/remainder in right places. 39/17,8*13/17,6 # Split out divisor/remainder for 2 terms. 2;5,8*13/17,6 # Move remainder right. 2,8*13/17 + 5,6 # Arithmetic. 2,104/17 + 5,6 # Arithmetic. 2,6 + 5;2, 6 # Arithmetic, move remainder right. 2,11,8 # Arithmetic. 2,B,8=2B8 # Get digits and reduce list to numeral. So I didn't need any arithmetic with any power of (13/17) above (13/17)^1. The trick is that we need to track divisors and remainders throughout the conversion and take the right actions with them. I'm not sure if I can describe this in general terms yet. I think I'll need to program it before I can give a more general description. Life is busy. That's going to take a while... Good thing no one is waiting for me to finish up. For comparison, here's Horner's method going from 13 to 10, then divide remainder to get from 10 to 17. I guess the divisions in divide/remainder might be much bigger than the divisions in the method above for large numerals. Not sure about that though. Horner's method 4 * 13 + 7 = 59 59 * 13 + 6 = 773 773 / 17 = 45;8 45 / 17 = 2;11 2,11,8 2,B,8=2B8 Update: Just for fun, the same example from base 13 to base 10... 476_13 to base 10 4,7,6 4(13/10)(13/10),7(13/10),6 52/10(13/10),91/10,6 [5;2](13/10),91/10 5(13/10),2(13/10)+(91/10),6 65/10,(26+91)/10,6 6;5,117/10,6 6,11;7 + 5,6 6,16;7,6 6;16,13 6;17,3 7,7,3 773_10 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DirectRecursive07Jul07

Jun_25_2007 Here's one where the number of digits changes. As suspected, the extra digit went away naturally... 111_7 to base 13 111_7 1,1,1 (7/13)(7/13), 7/13, 1 # This looks susceptible to recursion? 49/169, 7/13, 1 0;49, 7/13, 1 0, 56/13, 1 0, 4;4, 1 0, 4, 5 45_13 I want to claim that I'm not actually evaluating the polynomial in order to perform the conversion, I'm not entirely sure that's true though. And another just for fun, 111_7 to base 20 1,1,1 7*7/20*20, 7/20, 1 49/400, 7/20, 1 0;49, 7/20, 1 0, 56/20, 1 0, 2;16, 1 0, 2, 17 2H_20 and one more, reducing length by two digits, 212_3 to base 31 2, 1, 2 3*3/31*31, 3/31, 1 18/961, 3/31, 2 0;18, 3/31, 2 0, 21/31, 2 0, 0; 21, 2 0, 0, 23 N_31 Except for the size of the numbers in the product list, I kinda like this method. The growth rate in the product list is a problem though. For batch processing, it can be prefilled, so that's good. It still gets cumbersome though. How would Horner's method do 111_7 to base 13? 1 * 7 + 1 = 8 8 * 7 + 1 = 57 57 / 13 = 4;5 45_13 So even with prefilling the power list, Horner's method is still faster. Doesn't look promising. Oh well. At least it's fun. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Seven2Thirteen25June07

Jun_25_2007 And converting upwards directly between bases seems painless too. The method is identical. Here's an example from base 13 to base 17... 936_13 {9,3,6} # Explode numeral into a list of digits. {(13/17)(13/17),(13/17),1} # Multiply by corresponding powers # from list of powers of inbase/outbase 9*13*13/17*17,3*13/17,6 5;76, 39/17, 6 # Integer division, move remainder right. 5, 115/17, 6 # Another integer division. 5, 6; 13, 6 # Move remainder right. 5, 6, 19 # Normalize for base 17. 5, 7, 2 # Implode list to numeral. 572_17 It's interesting that I did the conversion, but still have no idea at all what this number is in base 10. I confirmed the conversion using DispConWeb- http://home.ccil.org/~remlaps/DispConWeb/ Let's figure it out in elisp... (+ (* 5 (expt 17 2)) (* 7 (expt 17 1)) (* 2 (expt 17 0))) 1566 (+ (* 9 (expt 13 2)) (* 3 (expt 13 1)) (* 6 (expt 13 0))) 1566 So: 5*17^2 + 7*17 + 2 = 1566 9*13^2 + 3*13 + 6 = 1566 I wonder... Can we revisit the related algorithm for integer multiples of bases and simplify it by using reciprocals and integer/remainder division? Can we reduce the size of the multiplications by some sort of mod operation on the powers list (doubtful)? Can we reduce the size/numbers of multiplications by reorganizing the expression recursively, as in Horner's method (synthetic division)? I haven't tried any examples, going up, where the number of digits changes, but I don't see any reason why it wouldn't work the same way. I think the extra digits should wash out naturally(?). Looks like I've got myself another programming project. Wonder what language I'll play with this time? Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#ConvertUp25June07

Jun_24_2007 I think I'm starting to get the hang of this... 311_13 3,1,1 169/49,13/7,1 # Powers of 13/7 507/49,13/7,1 # Multiply digits by powers. 10;17,13/7,1 # Divide left to right, move remainder rightwards. 10,30/7,1 # Keep dividing and moving right. 10,4;2,1 # Last time. 10,4,3 # Now normalize. Ten's too big in base 7. 1,3,4,3 1343_7 Based on the integer multiples of bases methods, I think going upwards is going to be trickier. As we can see, going down is actually pretty easy. I guess Horner's method going through base 10 is still probably easier though. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Example4-24June07

Jun_24_2007 And this one was painless. 111_13 1,1,1 169/49,13/7,1 # Powers of 13/7 169/49,13/7,1 # Multiply corresponding digits by powers. 3;22,13/7,1 # Divide left to right, carry remainder 3,35/7,1 # Keep going left to right, no need to carry 3,5,1 # All legal, no need to normalize. 351_7 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#RepOnes24June07

Jun_24_2007 Here's another one. Still making it up as I go... 1010_13 1,0,1,0 2197/343,169/49,13/7,1 2197/343,0,13/7,0 6;139,0,13/7,0 6,2;41,13/7,0 6,2,54/7,0 6,2,7,5 # Got a polynomial Now normalize 6,3,0,5 6305_7 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AnotherOne24June07

Jun_24_2007 Here's my first direct base to base conversion without an intermediate base or a power of Pascal's triangle. Still working out the details. I'm not quite sure what I did, but I haven't had any real time to look at it. This is a quick start just to get the ball rolling. Base 13 to base 7. a;b denotes integer;remainder results of division. 100_13 1,0,0 169/49,13/7,1/1 (powers of 13/7) 169/49,0,0 3;22,0,0 3,3;1,0 # move remainder rightwards.... 3,3,0;1 # seems like one of the positions disappeared somehow??? 331_7 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DirectConvert24June07

Jun_24_2007 Well it's been obvious for a while that it should work this way. This is the first time I've checked it though. Apparently we can convert directly from base B1 to base B2 without going through an intermediate base and without using a power of Pascal's triangle with matrix multiplication. Inbase: 7 Outbase: 13 Inbase/Outbase: 0.5385 Powers of Inbase/Outbase (Real / rounded): ___ {(7/13)^3, (7/13)^2, (7/13)^1, (7/13)^0}, ___ {0.1561, 0.2899, 0.5385, 1.0} So we take a polynomial... 3x^3 + 2x^2 + 4x + 3 = 1158_10 (x == 7) Multiply corresponding positions- ____{3.0, 2.0, 4.0, 3.0} # Coefficients of polynomial -*- {0.1561, 0.2899, 0.5385, 1.0} # Powers of inbase/outbase And get: {0.4684,0.5799,2.1538,3} Not surprisingly: 0.4684x^3 + 0.5799x^2 + 2.1538x + 3 (x==13) =~ 1158_10 (approximate due to rounding) It seems, then, that we can use InBase/OutBase or OutBase/Inbase with the previously described algorithms in order to convert directly between bases, regardless of whether the bases are integer multiples of each other or not. I haven't worked out the truncate/remainder logic yet, but I'm sure there must be logic available so that we can use integer arithmetic with borrowing and carrying in order to avoid floating point data and rounding. No telling how it will perform. I guess it'll be marginally better than going through an intermediate base, but maybe not. I'm also still wondering, occasionally, about using modulos in some way to reduce the size of the elements in the power array. It'll be a while before I find time to look at that again though. I'm not optomistic. (*** fyi- Previously described algorithms are here: http://home.ccil.org/~remlaps/AlternateBaseConversionAlgorithms.pdf and here: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#EconomicalGenericBaseConversion10June07 ***) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NonIntMultiples24June07

Jun_23_2007 Here's a side by side comparison of base conversion methods... http://home.ccil.org/~remlaps/CompareSteps.pdf Looks like Horner's method is faster than the ones I've been looking at and requires smaller multiplications/divisions, so it's preferred, with one possible exception... Blocks in grey are parallellizable and blocks in blue might be, although I'm not clear on that yet. There *may* be unusual cases (probably in the downward multiple case only) where normalization can be deferred and parallel processing can be used to outperform Horner's method. If digit normalization is required, Horner's will outperform. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#CompareTable22June07

Jun_18_2007 No use for it, except maybe to make it easier (shorter) to express negative numbers, but I wonder if there's a name for bases like the second one below... sort of complementary to negative bases. Negative binary 1 : 1 10 : -2 11 : -1 100 : 4 101 : 5 110 : 2 111 : 3 1000 : -8 1001 : -7 1010 : -10 1011 : -9 1100 : -4 1101 : -3 1110 : -6 1111 : -5 ... ... Unknown name 1 : -1 10 : 2 11 : 1 100 : -4 101 : -5 110 : -2 111 : -3 1000 : 8 1001 : 7 1010 : 10 1011 : 9 1100 : 4 1101 : 3 1110 : 6 1111 : 5 ... ... ... Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AnotherNegBase18June07

Jun_13_2007 For whatever it's worth... fun NormalDig (Digit, Base) = if ( Digit < Base ) then Digit :: [] else NormalDig (Digit div Base, Base) @ [Digit mod Base]; NormalDig (999...999, 2); in SML/NJ takes about 2 minutes and 20 seconds to convert 10^6912 - 1 from decimal to binary. http://home.ccil.org/~remlaps/DispConWeb takes about 15 seconds for the same conversion on the same computer. Surprisingly, reversing the conversion in DispConWeb takes about 15 seconds too. I would've thought that would take a noticable bit longer. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Performance13June07

http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FurtherReduced12June07 let: log_b1 = log (base b1), converting from base b1 through bm to b2 log_bm = log (base bm), converting from base b1 through bm to b2 log_b2 = log (base b2), converting from base b1 through bm to b2 If I'm thinking right, step 3 requires - 2 * ceiling(log_b1(N+1)) multiplications - ceiling(log_b1(N+1)) divisions - ceiling(log_b1(N+1)) additions step 4 requires - ceiling(log_bm(N+1)) multiplications - ceiling(log_b2(N+1)) divisions - ceiling(log_b2(N+1)) additions giving an upper boundary somewhere around 3 * ceiling(log_bx(N+1)) multiplications 2 * ceiling(log_bx(N+1)) divisions 2 * ceiling(log_bx(N+1)) additions Where x is the smallest of (b1|b2). We can forget about steps 1 and 2 since they only happen once. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#RunTime13June07

Jun_12_2007 http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#EconomicalGenericBaseConversion10June07 A possible improvement... I still have to work out the details; I've done it by hand, but I can't describe it yet. It seems that the multiply/divide actions in step 3 can be combined during one (left to right) pass through the numeral. Similarly, the multiply/normalize actions in step 4 can be combined into a single pass (right to left) through that first result. I think we actually only need two passes through the string to accomplish the conversion. (assuming precompletion of steps 1 and 2.) I don't think steps 3 and 4 can be usefully combined. If they can, I don't see how yet. The obstacles are The number of digits might change between the source base and the intermediate base. If it does, you can't simply multiple corresponding elements from L1 and L2; L2 needs to be shifted. But you don't know that until you complete the first conversion. (of course you could use the ceiling(log_B (N+1)) formula for number of digits, but I don't think you're going to save any time that way. I think it's probably trading complexity for nothing.) Division in step 3 has to happen left to right, but normalization in step 4 must happen right to left. Also, I should mention that in lieu of a common multiple, a common factor might also be used for the intermediate base. Performance-wise, I bet a common factor would be better, when available. i.e. Base 8 to base 12 could go through any of bases {2,4,24,36,72,...} Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FurtherReduced12June07

If we combine and simplify Algorithms 3 and 4 described in Alternate Algorithms for Integer Base Conversion and implemented at DispConWeb, we get another algorithm which might be useful for performing large numbers of base conversions between the same two bases if the bases are not multiples of one another. From 10 to 18 or 4 to 10, for example. I think this will be preferred over the equivalent offset based conversion by Pascal's triangle, even if the Pascal's triangle matrix is saved between conversions. An algorithm to convert a batch of numbers from base B1 to base B2 with the example of converting 187_10, 237_10 -> base 18. 1.)Find LCM(B1,B2), call it M. (or any multiple, really, B1 * B2 will do). A.example: i.B1=10, ii.B2=18 iii.M=LCM(B1,B2)=90 B. Done only once. 2.) Get powers of factors needed for subsequent conversions. A.Get lists of powers of M/B1 and M/B2. i.example: a.M/B1=90/10=9 b.M/B2=90/18=5 c.L1={1,9,81} d.L2={25,5,1} B.Three digits = three powers (^0,^1,^2) C.Done only once. 3.)Convert B1 to polynomial in terms of M using modified multiple of bases algorithm. A.Multiply digits of N_n by elements of L1 i.example: a.[{1,8,7};{2,3,7}] * {1,9,81} = [{1,72,567};{2,27,567}] B.Divide coefficients from B.) by highest power used from L1, multiply remainder by M and carry the product from left to right. i.example: a.[{1,72,567};{2,27,567}]/{81} = - [{0,162,567};{0,207,567} - [{0,2,567};{0,2,4617}] - [{0,2,7};{0,2,57} C. (0*90^2 + 2*90 + 7 = 187; 0*90^2 + 2*90 + 57 = 237) D. Normalization is not needed here. E. Performed once per number to be converted. 4.)Convert polynomial in terms of M to base B2 using multiple of bases algorithm. A.Multiply coefficients from C.) by elements of L2 i.example: [{0,2,7};{0,2,57}]*{25,5,1} = [{0,10,7};{0,10,57}] B.Normalize i.example: a.[{0,A,7};{0,D,3}] C. Performed once per number to be converted. So we see that 187_10 converts to A7_18 and 237_10 converts to D3_18. Discussion: When converting between bases which are not multiples of one another, it is always possible to convert through the base which is a Least Common Multiple of the two. When converting a large number of numerals, this can be economical for two reasons. First, assuming we know the maximum number of digits in the data, step 2. above only needs to be done once for each pair of bases, regardless of how many numerals are being converted. If we were naively implementing the previous multiple of bases algorithm, that step would be done twice per conversion (base B1 to M and base M to B2). This can save a large number of multiplications as the number of numerals and digits per numeral grow. Second, step 4B, Normalization, doesn't need to be done at the intermediate base. This saves one pass per numeral through the coefficient list over a naive implementation going from base B1 to M, then M to B2. The naive implementation would require digit normalization at the intermediate base (M). Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#EconomicalGenericBaseConversion10June07

Jun_09_2007 Updated DispConWeb: http://home.ccil.org/~remlaps/DispConWeb/ to include some error handling and to embed in the web page rather than launching in an external window. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#EmbeddedJava09June07

Jun_02_2007 I ported the base conversion tool to a web based app this week. Lots left to do, but here's a start. http://home.ccil.org/~remlaps/DispConWeb/index.html Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DispConWeb02Jun07

May_20_2007 Here's a function to normalize a coefficient for some base in CLISP. Syntax: (Normal [coefficient] [base]) (defun Normal (coeff base) (let ((div (values (floor coeff base))) (rem (nth-value 1 (floor coeff base)))) (if (< div base) (if (> div -1) (list div rem) (append (Normal div base) (list (abs rem)))) (append (Normal div base) (list rem))))) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#ClispNormal19May07

May_20_2007 Math functions and operators in various programming languages... http://merd.sourceforge.net/pixel/language-study/syntax-across-languages/Mthmt.html Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MathOpsProgramming20May07

May_17_2007 A elisp function to convert a base 10 numeral into a list of base 10 digits. No error checking. (defun asc-to-char (X) (if (equal X nil) nil (cons (- (car X) 48) (asc-to-char (cdr X)) ) ) ) (asc-to-char (string-to-list "10743201")) (1 0 7 4 3 2 0 1) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#StringToNumeral17may07

May_14_2007 (defun Normal (coeff base) (let ((div (/ coeff base)) (rem (% coeff base))) (if (< div base) (if (> div -1) (list div rem) (append (Normal div base) (list (abs rem)))) (append (Normal div base) (list rem))))) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#LispNormal13May07

May_12_2007 I wonder what happens if you multiply digits of a numeral by corresponding terms of the fibonacci sequence, then normalize the result into digits in some base. Probably nothing interesting. Here are a couple examples, starting from 9999. I don't see anything in them yet... 9,9,9,9 1,1,2,3 9,9,18,27 9,9,20,7 # Base 10 9,11,0,7 10,1,0,7 1,0,1,0,7 9,9,18,27 9,9,31,1 # Base 2 9,24,1,1 21,0,1,1 10,1,0,1,1 5,0,1,0,1,1 2,1,0,1,0,1,1 1,0,1,0,1,0,1,1 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NormalFib12May07

May_09_2007 As before, but normalizing to base 3 gives this sequence... http://www.research.att.com/~njas/sequences/A081568 1,2,1 1,1,2 1,2,2 - 17_10 1,3,3,1 1,1,2,3 1,3,6,3 1,3,7,0 1,5,1,0 2,2,1,0 - 75_10 1,4,6,4,1 1,1,2,3,5 1,4,12,12,5 1,4,12,13,2 1,4,16,1,2 1,9,1,1,2 4,0,1,1,2 1,1,0,1,1,2 - 338_10 Haven't checked with fibonacci numbers going right to left. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MorePascalFib09May07

May_09_2007 Take rows of Pascal's triangle, multiply digits by the fibonacci numbers, then normalize into binary, then convert to decimal. You get this sequence http://www.research.att.com/~njas/sequences/A081567 The sequence with fibonacci numbers reversed isn't listed in AT&T (1,3,7,55,233,987,...) Let *$ operator == multiply terms, then normalize. Rows of Pascal's triangle *$ Fibonacci numbers left to right. 1 1 1 - 1_10 1,1 1,1 - 3_10 1,2,1 1,1,2 1,2,2 1,3,0 2,1,0 1,0,1,0 - 10_10 1,3,3,1 1,1,2,3 1,3,6,3 1,3,7,1 1,6,1,1 4,0,1,1 2,0,0,1,1 1,0,0,0,1,1 - 35_10 1,4,6,4,1 1,1,2,3,5 1,4,12,12,5 1,4,12,14,1 1,4,19,0,1 1,13,1,0,1 7,1,1,0,1 3,1,1,1,0,1 1,1,1,1,1,0,1 - 125_10 1,5,10,10,5,1 1,1,2,3,5,8 1,5,20,30,25,8 1,5,20,30,29,0 1,5,20,44,1,0 1,5,42,0,1,0 1,26,0,0,1,0 14,0,0,0,1,0 7,0,0,0,0,1,0 3,1,0,0,0,0,1,0 1,1,1,0,0,0,0,1,0 - 450_10 1,6,15,20,15,6,1 1,1,2,3,5,8,13 1,6,30,60,75,48,13 1,6,30,60,75,54,1 1,6,30,60,102,0,1 1,6,30,111,0,0,1 1,6,85,1,0,0,1 1,48,1,1,0,0,1 25,0,1,1,0,0,1 12,1,0,1,1,0,0,1 6,0,1,0,1,1,0,0,1 3,0,0,1,0,1,1,0,0,1 1,1,0,0,1,0,1,1,0,0,1 - 1625_10 Rows of Pascal's triangle *$ Fibonacci numbers left to right. 1,2,1 2,1,1 2,2,1 3,0,1 1,1,0,1 - 7_10 1,3,3,1 3,2,1,1 3,6,3,1 3,7,1,1 6,1,1,1 3,0,1,1,1 1,1,0,1,1,1 - 55_10 1,4,6,4,1 5,3,2,1,1 5,12,12,4,1 5,12,14,0,1 5,19,0,0,1 14,1,0,0,1 7,0,1,0,0,1 3,1,0,1,0,0,1 1,1,1,0,1,0,0,1 - 233_10 1,5,10,10,5,1 8,5,3,2,1,1 8,25,30,20,5,1 8,25,30,22,1,1 8,25,41,0,1,1 8,45,1,0,1,1 30,1,1,0,1,1 15,0,1,1,0,1,1 7,1,0,1,1,0,1,1 1,1,1,1,0,1,1,0,1,1 - 987_10 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PascalAndFib09May07

Apr_29_2007 Here's a first pass at a GUI for base conversion with bases 2 through 94 and -2 through -94. The java GUI is constructed using swing, from the Java Foundation Classes (JFC). http://home.ccil.org/~remlaps/DispCon To compile it myself, download all *.java files then do: javac PascalT.java javac Normalize.java javac DispCon.java java -cp . DispCon # Updated April 30 with -cp . option To use pre-compiled files, download everything and do: java -cp . DispCon # Updated April 30 with -cp . option Base conversion algorithm descriptions are the same three I've been writing about. Pascal's Triangle when bases are offset by B +/- N. Powers of N when bases are multiples of each other. http://home.ccil.org/~remlaps/http://home.ccil.org/~remlaps/AlternateBaseConversionAlgorithms.pdf I'm still weak with java, but it is what it is. The point was to implement the algorithms. Pretty code might come later. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DispConV0-29Apr07

Apr_27_2007 Speaking of Pascal's Triangle, from a prime number mailing list I lurk on... http://www.individual.utoronto.ca/levenson/nnd.htm Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PascalPrime27Apr07

Apr_14_2007 This isn't what I was expecting at all. Instead of reversing the digits, reverse the order of digits.... Here's the addition table. Normal digit order in columns, reverse digit order in rows (result in normal digit order...) 0 ---- 1 ---- 2 ---- 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 9 0 ---- 1 ---- 2 ---- 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 8 1 ---- 2 ---- 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 ---- 1,0 7 2 ---- 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 6 3 ---- 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 5 4 ---- 5 ---- 6 ---- 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 4 5 ---- 6 ---- 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 -- 1,4 3 6 ---- 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 -- 1,4 -- 1,5 2 7 ---- 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 -- 1,4 -- 1,5 -- 1,6 1 8 ---- 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 -- 1,4 -- 1,5 -- 1,6 -- 1,7 0 9 ---- 1,0 -- 1,1 -- 1,2 -- 1,3 -- 1,4 -- 1,5 -- 1,6 -- 1,7 -- 1,8 1,9,6 1,9,6 ----- 9,9,9 So any number added to itself this way gives 9,9,...,9 Useless I suppose. Negative results should be recorded though. I wonder what I'd need to add to 196, in this fashion to get 887? 1,9,6 3,0,8 ----- 8,8,7 (or 1,1,2) That doesn't jump out at me as interesting. What do I need to add to 887 to get 1675? 8,8,7 2,1,1 ----- 1,6,7,5 (or 8,3,2,4 ; -) Still nothing.... 3,0,8 is 6,9,1 with the rearranged digits and 2,1,1 is 7,8,8 with rearranged digits. So I guess that makes sense. Guess I was thinking wrong. ==- 1,6,7,5 4,2,3,8 ------- 6,[1,3],[1,3],6 6,[1,4],3,6 7,4,3,6 We can do the reverse and add operation this way, but I don't see that it buys anything. Either way, we're reversing digits and applying an addition table. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Surprise041407

Apr_04_2007 Found two numbers which can be reached 10 ways by N + N_r where N_r is N with its digits reversed. Count: 10 --- Max Target: 1111, Max Count: 10 Count: 10 --- Max Target: 1991, Max Count: 10 That sequence is here: http://www.research.att.com/~njas/sequences/A072434 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#RevTenCount040407

Apr_03_2007 Numbers which can be expressed as N + N_r in 9 ways where N_r is N with it's digits reversed. Count: 9 --- Max Target: 99, Max Count: 9 Count: 9 --- Max Target: 110, Max Count: 9 Count: 9 --- Max Target: 121, Max Count: 9 Count: 9 --- Max Target: 909, Max Count: 9 Count: 9 --- Max Target: 929, Max Count: 9 Count: 9 --- Max Target: 949, Max Count: 9 Count: 9 --- Max Target: 969, Max Count: 9 Count: 9 --- Max Target: 989, Max Count: 9 So far, 9 is the most I've found and 989 is the highest. They're here already: http://www.research.att.com/~njas/sequences/A072433 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#RevSums040307

Mar_27_2007 Here's another potential method for identifying stable conversions. Completely untested so far. A guess... == Let ___ N be a numeral ___ B and B' be bases, B < B' ___ C <- N_B converted to base B+1 ___ C' <- N_B' converted to base B'+1 Then ___ if C =~ C', N_B is a stable conversion. (=~ string match) == If that's right, then I can convert .. R1 <- N_B to N_B+1 -and- .. R2 <- N_B+1 to N_B+2 If R1 =~ R2 (string compare), it's a stable conversion. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#StableConversions032707

Mar_25_2007 Another way of looking at stable conversions... (Stable conversions are still what I'm calling conversions which are the same over an offset, regardless of what the source base is. i.e. 1455_B goes to 1103_(B+1) whenever B is above 5. There are stable conversions for other offsets, but I'm just looking at (from B to B+1) right now. I once listed sequences by base here: http://home.ccil.org/~remlaps/weblog_2006/mathematics_index.html#SteadySeries111606 At the time, AT&T didn't have any of them. I don't know if they have 'em now or not. *** Reminder, AT&T is here: http://www.research.att.com/~njas/sequences/index.html *** And here's the way I was thinking about stable conversions this afternoon... D = Decimal Representation B = Base where the number becomes a stable conversion from base B to B+1. Rep = Representation in base B. D - B (Rep) 0 - 1 (0) 1 - 1 (1) 2 - 3 (2) 3 - 2 (11) 4 - 3 (12) 5 - 4 (11) 6 - 4 (12) 7 - 4 (13) 8 - 5 (12) 9 - 5 (14) 10 - 4 (22) 11 - 4 (23) 12 - 5 (22) 13 - 5 (23) 14 - 5 (24) 15 - 4 (33) 16 - 3 (121) 17 - 3 (122) 18 - 5 (33) 19 - 5 (34) 20 - 7 (26) 21 - 6 (33) ... Sequence: 1,1,3,2,3,4,4,4,5,5,4,4,5... is not found at AT&T Neither is 0,1,2,11,12,11,12,13,12,14,22,23,22... Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#SteadyConversionsRedux032507

Mar_05_2007 I think I've got the algorithms I'm playing with for base conversion all working in one place. Much clean-up is needed, but here's a bare-bones, working, couple of programs.... http://home.ccil.org/~remlaps/src/normalize.java.txt http://home.ccil.org/~remlaps/src/PascalT.java.txt To compile them, download and save as normalize.java and PascalT.java, then do: $ javac normalize.java PascalT.java $ java normalize then follow prompts. (I guess the java jdk is needed, from java.com) When one base is a multiple of another, it'll use the appropriate multiple of bases algorithms. When one base is not a multiple of another, it will convert using the offset to create a Pascal's Triangle matrix to the required power. // Reminder... algorithm descriptions are started here: AlternateBaseConversionAlgorithms.pdf Here's a sample run showing positive and negative offsets, source multiple of target and target as multiple of source. It ends up at the same place it started, so they all appear to be working.... c:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 1234 Enter an input base: 90 Enter an output base: -89 1 2 3 4 90 is not a multiple of -89 1 537 96123 5735339 0 1 358 32041 0 0 1 179 0 0 0 1 Result is: 1 539 96842 5799962 Converts to: 1<6]A Enter a numeral: 1<6]A Enter an input base: -89 Enter an output base: 88 1 88 6 79 10 -89 is not a multiple of 88 1 -708 187974 -22180932 981506241 0 1 -531 93987 -5545233 0 0 1 -354 31329 0 0 0 1 -177 0 0 0 0 1 Result is: 1 -620 141252 -13912121 493699738 Converts to: 18NQ Enter a numeral: 18NQ Enter an input base: 88 Enter an output base: 2 Converts to: 10110110000000000010 Enter a numeral: 10110110000000000010 Enter an input base: 2 Enter an output base: 90 Converts to: 1234 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AllTogether030507

Feb_20_2007 A start on describing the base conversion algorithms I've been playing with. http://home.ccil.org/~remlaps/AlternateBaseConversionAlgorithms.pdf Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AlternateAlgorithms022007

Feb_18_2007 I'm starting to think about how to describe the conversion between bases which are multiples of one another. Here's a first pass, explaining it by example... Base 10 to base 2... 0.) Start with: 1776_10 1.) Split into digits: {1,7,7,6} 2.) Get increasing powers of 10/2 = 5 (right to left): {125,25,5,1} 3.) Multiply digits by corresponding powers of 5: {125,175,35,6} 4.) Normalize into base 2 by "carrying" (if needed) {125,175,35,6} -> {125, 175, 38, 0} # 38 = 35 + 3 -> {125, 194, 0, 0} # 194 = 175 + 19 -> {222, 0, 0, 0} # 222 = 125 + 97 -> {111, 0, 0, 0, 0} # 111 is a new place -> {55, 1, 0, 0, 0, 0} # 55 is a new place -> {27, 1, 1, 0, 0, 0, 0} # 27 is a new place -> {13, 1, 1, 1, 0, 0, 0, 0} # ... -> {6, 1, 1, 1, 1, 0, 0, 0, 0} # ... -> {3, 0, 1, 1, 1, 1, 0, 0, 0, 0} # ... -> {1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0} # ... So 1776_10 == 11011110000_2 Base 2 to base 10... 0.) Start with: 1011 1.) Split into digits: {1,0,1,1} 2.) Get increasing powers of 10/2 = 5 (left to right): {1,5,25,125} 3.) Multiply digits by corresponding powers of 5: {1,0,25,125} 4.) Divide each place by 125, borrow remainder: {1,0,25,125} -> {0,10,25,125} # 10 = 10 * 1 + 0 -> {0,0,125,125} # 125 = 10 * 10 + 25 -> {0,0,1,125} # 1 = 125/125 -> {0,0,1,1} # 1 = 125/125 So 1011_2 = 11_10. 5.) Digit normalization(not needed for this example). Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#DescribeFactorConversion021807

Feb_17_2007 Of absolutely no use, here's another possible number system. In addition to positive and negative bases, there's the possibliity of starting negative bases at -1 instead of 1. Here's counting to 16 in that numeration system... Inverse negative binary counting 11 : 2-1 = 1 10 : 2-0 = 2 1101 : 8-4-1 = 3 1100 : 8-4 = 4 1111 : 8-4+2-1 = 5 1110 : 8-4+2 = 6 1001 : 8-1 = 7 1000 : 8 = 8 1011 : 8+2-1 = 9 1010 : 8+2 = 10 1101 : 8+3 = 11 110100 : 32-16-4 = 12 # 110111 : 12 + 1 = 13 110110 : 12 + 2 = 14 # 110001 : 32-16-1 = 15 110000 : 32-16 = 16 The series: 11,10,1101,1100,1111,1110,1001,1000,1011,1010,1101,110100 is not listed in AT&T. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#InverseNegBinary021806

Feb_16_2007 I've updated normalize.java to handle positive integers in negative bases (I think)... http://home.ccil.org/~remlaps/src/normalize.java.txt Here are some samples... c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 10011 Enter an input base: 2 Enter an output base: 64 Converts to: J c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: J Enter an input base: 64 Enter an output base: -8 Converts to: 163 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 163 Enter an input base: -8 Enter an output base: 4 Converts to: 103 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 103 Enter an input base: 4 Enter an output base: -72 Converts to: J c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: J Enter an input base: -72 Enter an output base: -2 Converts to: 10111 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 10111 Enter an input base: -2 Enter an output base: 2 Converts to: 10011 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 Enter an input base: 8 Enter an output base: 64 Converts to: 199999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 199999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 Enter an input base: 64 Enter an output base: -64 Converts to: 2tAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAt9 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 2tAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAtAt9 Enter an input base: -64 Enter an output base: -8 Converts to: 27272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727271 c:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 27272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727271 Enter an input base: -8 Enter an output base: 8 Converts to: 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#UpdatedJava021607

Feb_16_2007 Apparently, what I already wrote handles negative to positive base conversions of positive integers just fine (That's handy.). Doesn't work for negative integers or going to negative bases though... Normalization needs to be modified for negative bases and I'm not even thinking about negative integers. Here are some sample conversions from negative to positive bases... C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 111 Enter an input base: -2 Enter an output base: 2 Converts to: 11 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 216 Enter an input base: -10 Enter an output base: 10 Converts to: 196 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 102030405060708 Enter an input base: -9 Enter an output base: 9 Converts to: 102030405060708 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 121 Enter an input base: -3 Enter an output base: 3 Converts to: 11 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 1111111 Enter an input base: -2 Enter an output base: 10 Converts to: 43 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 196 Enter an input base: -10 Enter an output base: 10 Converts to: 16 C:\Personal\Steve\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 196 Enter an input base: -10 Enter an output base: 2 Converts to: 10000 Now that's cool. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NegToPosBase021607

Feb_16_2007 And even better... The previous conversion from base 10 to base -10 exploited the fact that 10 - 20=-10. Here's one that explots 10 * (-1) = -10. {1,9,6} o {1,-1,1} => {1,-9,6} (look familiar?) Using the same digit normalization rules (which I still don't know), gives {1+1,-9+10,6} = {2,1,6} = 2(10^2) - 1(10) + 6 = 196. Much simpler. Now I just need to figure out what I'm doing for digit normalization. I suppose I'm just reversing signs from positive base normalization, but I'm not sure about that. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MoreNegBase021606

Feb_16_2007 So how 'bout going from base 10 to base -10? [1,2,1 0,1,1 0,0,1]^20 = [1,40,400 0, 1, 20 0, 0, 1] [1,9,6] * [1,40,40,...] = [1,49,586] Digit normalization is a little different and I can't quite explain it yet, but it seems to apply (based on exactly 1 observed conversion ;-) 1*100 - 49(10) + 586 = 100 - 490 + 586 = 196 [1,49,586] -> [1,(49 - 58),6] -> [1, -9, 6] -> [2, 1, 6] == 2*100 + (-1)10 + 6 = 196 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NegBase021607

Feb_11_2007 I updated the normalize.java file to perform base conversion all the way from string to string. Here's the code: http://home.ccil.org/~remlaps/src/normalize.java.txt And here's a sample run that starts and ends with 1025_10. C:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 1025 Enter an input base: 10 Enter an output base: 2 Converts to: 10000000001 C:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 10000000001 Enter an input base: 2 Enter an output base: 90 Converts to: BZ C:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: BZ Enter an input base: 90 Enter an output base: 45 Converts to: MZ C:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: MZ Enter an input base: 45 Enter an output base: 5 Converts to: 13100 C:\Personal\programming\java>java normalize 1 2 3 4 5 6 7 8 9 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[]{}\|;:,.<>/?'" Enter a numeral: 13100 Enter an input base: 5 Enter an output base: 10 Converts to: 1025 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NormalUpdated021107

Feb_10_2007 I'm still working on the code, but I've got java code running to do digit based integer base conversion algorithm where one base is a multiple of another. Here's sample output from base 10 to base 190, then 190 to 19. Confirmed by a divide/remainder conversion from 10 to 19. /* * Base 10 to base 19. */ C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 1 0 4 4 3 7 7 2 Enter an input base: 10 Enter an output base: 190 Normalizes to: [0 0 0 0 1 99 57 42] /* * Base 190 to base 19. */ C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 1 99 57 42 Enter an input base: 190 Enter an output base: 19 Normalizes to: [4 4 2 12 2 4] /* * Verification */ - B2B("10443772",10,19,true); val it = "442C24" : string /* * To-do */ Add integer base conversion by Pascal's triangle for direct conversion when one base is not a multiple of the other. Here's the (still sloppy) code that performs the conversion. Normalize.java Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NormalBaseConversion021007

Feb_05_2007 http://www.maa.org/devlin/devlinfeb.html > 2 gills = 1 chopin, 2 chopins = 1 pint, 2 pints = 1 quart, 2 quarts = 1 > pottle, 2 pottles = 1 gallon, 2 gallons = 1 peck, 2 pecks = 1 > demibushel, 2 demibushels = 1 bushel or firkin, 2 firkins = 1 kilderkin, > 2 kilderkins = 1 barrel, 2 barrels = 1 hogshead, 2 hogsheads = 1 pipe, 2 > pipes = 1 tun. pottle is the one I think I was trying to remember. Maybe now I'll remember it, or at least know where to look for it. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#OldBinary020507

Feb_04_2007 Here's Pascal's Triangle with each row normalized for base 2... ....1 - 1 ....3 - 1 1 ....9 - 1 0 0 1 ...27 - 1 1 0 1 1 ...81 - 1 0 1 0 0 0 1 ..243 - 1 1 1 1 0 0 1 1 ..729 - 1 0 1 1 0 1 1 0 0 1 .2187 - 1 0 0 0 1 0 0 0 1 0 1 1 .6561 - 1 1 0 0 1 1 0 1 0 0 0 0 1 19683 - 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 59049 - 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 Sums of the rows are: 1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, ... Which is here: http://www.research.att.com/~njas/sequences/A011754 (Numbers of ones in binary expansion of 3^n) Which got me to notice that the rows are consecutive powers of 3. Same thing with base 3. Normalizing for base 3 gives consecutive powers of 4 in the rows. ( 1 1 1 1 2 1 2 1 0 1 1 0 0 1 1 1 [== B4{1,4,16,64,256,...} .== Sums{1,2,4,4,4,...}] ) Maybe Pascal's Triangle without normalization is kind-of equivalent to unary, and so it gives back consecutive powers of 2. I guess the powers of higher numbers is just a different way of observing the same principle/identities that I've been using for base conversion from base B to (B +/- 1). I just noticed that 14641_7 = 4096_10 (=8^4) and I'll bet 1331_7 = 512. Yup and of course, 121_7 = 64. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PTNormal020407

Feb_04_2007 So if I normalize the fibonnaci numbers backwards in some base and take consective results, one over the other, it looks like the ratio approaches phi*base. I'm not sure if that should have been obvious or not. # Base 10 C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 144 89 55 34 21 13 8 5 3 2 1 1 [144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Enter a base: 10 1 5 3 4 8 6 2 3 8 5 3 2 1 1 C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 233 144 89 55 34 21 13 8 5 3 2 1 1 [233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Enter a base: 10 2 4 8 3 4 8 6 2 3 8 5 3 2 1 1 (/ 15348623853211.0 948623853211.0) 16.17988394584154 (/ 248348623853211.0 15348623853211.0) 16.180514046622843 # Base 2 C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 233 144 89 55 34 21 13 8 5 3 2 1 1 [233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Enter a base: 2 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 C:\Personal\programming\java>java normalize Enter a [space] separated list of coefficients: 144 89 55 34 21 13 8 5 3 2 1 1 [144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1] Enter a base: 2 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 (/ 1381171.0 426803.0) 3.236085500804821 (* phi 2) 3.23606797749979 # Base 3 (without showing normalization) (/ 155953777.0 32128024.0) 4.854135349251482 (* phi 3) 4.854101966249685 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NormalFib020407

Feb_04_2007 Here's an elisp function for converting the terms of an 8 term polynomial downwards. (defun BoverN (d7 d6 d5 d4 d3 d2 d1 d0 Divisor) (list (* d7 (expt Divisor 7)) (* d6 (expt Divisor 6)) (* d5 (expt Divisor 5)) (* d4 (expt Divisor 4)) (* d3 (expt Divisor 3)) (* d2 (expt Divisor 2)) (* d1 Divisor) d0)) (BoverN 7 4 3 2 5 9 9 1 5) (546875 62500 9375 1250 625 225 45 1) Following that by a rough java program which normalizes digits goes like this... (I'll post the java code somewhere or other after refinement. Too much clutter for now.) C:\Personal\programming\java>java normalize java normalize Enter a [space] separated list of coefficients: 546875 62500 9375 1250 625 225 45 1 546875 62500 9375 1250 625 225 45 1 [546875, 62500, 9375, 1250, 625, 225, 45, 1] Enter a base: 2 2 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 And that matches B2B from my thesis: - B2B("74325991",10,2,true); val it = "100011011100001111111100111" : string A touch faster, for whatever that's worth... (nothing) And the same process works for base 10 to base 5... (BoverN 8 5 3 2 8 5 2 3 2) (1024 320 96 32 64 20 4 3) C:\Personal\programming\java>java normalize java normalize Enter a [space] separated list of coefficients: 1024 320 96 32 64 20 4 3 1024 320 96 32 64 20 4 3 [1024, 320, 96, 32, 64, 20, 4, 3] Enter a base: 5 5 1 3 3 3 2 1 0 0 3 0 4 3 - B2B("85328523",10,5,true); val it = "133321003043" : string Pretty cool! Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#BaseConvertAgain020407

Feb_04_2007 I'm not aware of any use for it, but I'm realizing tht digit normalization can be applied to any polynomial... Some sequences for fun (barring typos, programming errors or transciption errors). (example...) 5x^2 + 3x + 2 normalizes for base 2 as follows: =5,3,2 2(2^0) -> 1(2^1) =5,4,0 2(2^1) -> 1(2^2) =7,0,0 6(2^2) + 1(2^2) -> 3(2^3) + 1(2^2) =3,1,0,0 2(2^3) + 1(2^3) -> 1(2^4) + 1(2^3) =1,1,1,0,0 2^4 + 2^3 + 2^2 + 0 + 0 = 5(2)^2 + 3(2) + 2 (= 28) Primes as coefficients of polynomials, normalized to base 2.. Backwards: 2 - 1 0 (2) 3 2 - 1 0 0 0 (8) 5 3 2 - 1 1 1 0 0 (28) 7 5 3 2 - 1 0 1 0 1 0 0 (84) 11 7 5 3 2 - 1 0 0 0 0 0 1 0 0 (260) 13 11 7 5 3 2 - 1 0 1 0 1 0 0 1 0 0 (676) 17 13 11 7 5 3 2 - 1 1 0 1 1 1 0 0 1 0 0 (1764) 19 17 13 11 7 5 3 2 - 1 0 0 0 0 0 1 1 0 0 1 0 0 (4196) 23 19 17 13 11 7 5 3 2 - 1 0 0 1 1 1 0 1 1 0 0 1 0 0 (10084) Frontwards: (AT&T has this one in base 10: http://www.research.att.com/~njas/sequences/A110299) 2 - 1 0 (2) 2 3 - 1 1 1 (7) 2 3 5 - 1 0 0 1 1 (19) 2 3 5 7 - 1 0 1 1 0 1 (45) 2 3 5 7 11 - 1 1 0 0 1 0 1 (101) 2 3 5 7 11 13 - 1 1 0 1 0 1 1 1 (215) 2 3 5 7 11 13 17 - 1 1 0 1 1 1 1 1 1 (447) 2 3 5 7 11 13 17 19 - 1 1 1 0 0 1 0 0 0 1 (913) 2 3 5 7 11 13 17 19 23 - 1 1 1 0 0 1 1 1 0 0 1 Fibonacci numbers as coefficients of polynomials and normalized to base 2. Frontwards: 1 - 1 (1) 1 1 - 1 1 (3) 1 1 2 - 1 0 0 0 (8) 1 1 2 3 - 1 1 0 0 1 (25) 1 1 2 3 5 - 1 0 1 0 1 1 (43) 1 1 2 3 5 8 - 1 0 1 1 1 1 0 (46) 1 1 2 3 5 8 13 - 1 1 0 0 1 0 0 1 (201) 1 1 2 3 5 8 13 21 - 1 1 0 1 0 0 1 1 1 (423) 1 1 2 3 5 8 13 21 34 - 1 1 0 1 1 1 0 0 0 0 (880) 1 1 2 3 5 8 13 21 34 55 - 1 1 1 0 0 0 1 0 1 1 1 (1815) Backwards: 1 - 1 (1) 1 1 - 1 1 (3) 2 1 1 - 1 0 1 1 (11) 3 2 1 1 - 1 0 0 0 1 1 (35) 5 3 2 1 1 - 1 1 1 0 0 1 1 (115) 8 5 3 2 1 1 - 1 0 1 1 1 0 0 1 1 (371) 13 8 5 3 2 1 1 - 1 0 0 1 0 1 1 0 0 1 1 (603) 21 13 8 5 3 2 1 1 - 1 1 1 1 0 0 1 1 0 0 1 1 (3891) 34 21 13 8 5 3 2 1 1 - 1 1 0 0 0 1 0 0 1 1 0 0 1 1 (12595) 55 34 21 13 8 5 3 2 1 1 - 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 (40755) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FunNormalizedSequences020407

Jan_28_2007 Here's some sloppy java code I slapped together today to demo the full decimal to binary conversion. Needs to be padded with lots of leading 0's. http://home.ccil.org/~remlaps/src/Dec2BinR.java.txt And here's a sample conversion from 172 to 10101100 Give me a base 10 integer: 000000000172 0 0 0 0 0 0 0 0 0 25 35 2 000010101100 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#JavaDemo012806

Jan_28_2007 I was thinking that there are 8 possible orientations for pascal's triangle in a square matrix. There's plenty of room to play then. Multiplying this one... ... ... ... ... 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 by this one... ... ... ... ... 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 (It can be done here, for example) http://wims.unice.fr/wims/wims.cgi Gives an interesting looking answer. http://www.research.att.com/~njas/sequences/A000984 matches the top-left to bottom-right diagonal: 1,2,6,20,70. ("Central binomial coefficients") Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PTOrientations012806

Jan_27_2007 Here's an elisp example of decimal to binary conversion without digit normalization... OK it doesn't really look like binary without that normalization, so we'll have to imagine that step for now. Still, a careful look verifies the math. As we see, for a 5 digit number, 625.d4 + 125.d3 + 25.d2 + 5.d1 + d0 where d_i are base 10 digits gives an equivalent polynimial where variables are powers of 2. The "(print" line prints the coefficents. The "(+ " line does the math to verify the result. (defun d2b (d4 d3 d2 d1 d0) (print (list (* d4 625) (* d3 125) (* d2 25) (* d1 5) d0)) (+ (* d4 625 (expt 2 4)) (* d3 125 (expt 2 3)) (* d2 25 (expt 2 2)) (* d1 5 2) d0)) (d2b 7 0 5 6 3) (4375 0 125 30 3) 70563 (d2b 1 4 7 3 2) (625 500 175 15 2) 14732 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Dec2Bin012706

Jan_27_2007 (defun b20 (a b c d) (+ (* a 20 20 20) (* b 20 20) (* c 20) d)) (defun b22b (d1 d2 d3 d4) (list d1 (* 2 d2) (* 4 d3) (* 8 d4))) (b22b 9 4 3 1) (9 8 12 8) (/ (b20 9 8 12 8) 8) 9431 Digit normalization needs to be worked out, but base conversion seems almost straight-forward. And incidentally, the same principle appears to work for base b to base b/3 conversions with a matrix like this... 27,0,0,0 0,9,0,0 0,0,3,0 0,0,0,1 These can obviously be simplified: b to b/2 = 8d3 + 4d2 + 2d1 + d0 b to b/3 = 27d3 + 9d2 + 3d1 + d0 Followed by digit normalization. I assume it works similarly for any multiples of bases. So seemingly we can do decimal to binary as: ... + 625d4 + 125d3 + 25d2 + 5d1 + d0 Followed by digit normalization. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MultiplesOfBases012707

Jan_27_2007 OK, so M^-1 is .25,0,0 0,.5,0 0,0,1 That seems to work, but I want integers, not fractions. So how 'bout multiplying that matrix by 4 (or 8, or whatever... 2^[#digits-1]). N_10=[7,8,3] M1={ [1,0,0 _0,2,0 _0,0,4] } ( N_10 * M1 ) = [7,16,12] ((7 * 20^2) + (16 * 20) + 12) = 3132 Then dividing 4 back out of the result gives 783. Just what I was hoping to see. The basic digit normalization isn't gonna work here though. 7/4 is not an integer. That's bad. 7/4 = 1 + 3/4. 3/4 in the previous place is 15(20^j-1), so: 7,16,12 gives back =trunc(7/4),(remainder 7/4)*20 + 16/4, 12/4 =1,15 + 4,3 =1,19,3 It seems to work. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AnotherMatrix012707

Jan_27_2007 This looks promising... N_10=[9,3,4] M={ [4,0,0 _0,2,0 _0,0,1] } N_10 * M = [36,6,4] (36 * 5^2) + (6 * 5) + 4 = 934 It's backwards from the way I wanted to go, but it looks like multiplying a matrix comprised of digits by a matrix formed like M, then doing digit normalization might take a numeral from base B to base B/2 (for even B's). Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Bto2B-012707

Jan_26_2007 I was thinking on my way home tonight. Say, hypothetically, Someone wants to convert between two bases that are far away from each other. They could, conceivably, combine the digit-grouping method for powers of bases and the Pascal's triangle method for offsets. I wonder how that would perform. For example, to convert base 10 to base 4721, someone could do it like this... o Base 10 to base 8 via Pascal's Triangle ([PT]^2). o Base 8 to base 64 via digit grouping. (8^2) o Base 64 to base 69 via Pascal's Triangle ([PT]^-5). o Base 69 to base 4761 via digit grouping. (69^2) o Base 4761 to base 4721 via Pascal's Triangle([PT]^40) ___ That's ugly, but maybe not as bad as division by 4721^[successive_powers] ___ I think values in [PT]^40 still fit in 16bit integers at 6 digits. ___ Base 4721 overflows 16 bits in 3 digits. So it's a more complicated process, but I still wonder if it might be faster then divide/remainder since the changes in order of magnitude take essentially no time at all. Relatively speaking, the Pascal's Triangle steps are between bases that are somewhat close together. That wouldn't be true for the divide/remainder method. Also, I wonder if there's a general method for converting from base B to base 2B. Obviously, Pascal's triangle (to the -B power) works, but the actual array values are tied to the base. But could there be a method that doesn't depend on the base? It doesn't seem likely though. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#CombineMethods012607

Jan_25_2007 Pretty cool! The next diagonal: 16,80,240,560,1120,2016,3360,5280,.. divided by 8 gives back: 2,10,30,70,140,252,420,660,... Which is found here: http://www.research.att.com/~njas/sequences/A034827 2*C(n,4) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#AnotherDiag012507

Jan_25_2007 So I noticed that 8, 32, 80, 160, 280, 448, ... Are all multiples of 8. Divided by 8, the series is: 1, 4, 10, 20, 40, 56, ... Those, according to AT&T are tetrahedral numbers. http://www.research.att.com/~njas/sequences/A000292 (n * (n+1) * (n+2))/6 So that clued me in to 4n(n+1)(n+2)/3 for the next diagonal in the Pascal's Triangle squared matrix. (defun b (n) (/ (* 4 (* n (+ n 1) (+ n 2))) 3)) (b 1) 8 (b 2) 32 (b 3) 80 (b 4) 160 (b 5) 280 (b 6) 448 (b 7) 672 (b 8) 960 1 20 180 960 3360 8064 13440 15360 11520 5120 1024 0 1 18 144 672 2016 4032 5376 4608 2304 512 0 0 1 16 112 448 1120 1792 1792 1024 256 0 0 0 1 14 84 280 560 672 448 128 0 0 0 0 1 12 60 160 240 192 64 0 0 0 0 0 1 10 40 80 80 32 0 0 0 0 0 0 1 8 24 32 16 0 0 0 0 0 0 0 1 6 12 8 0 0 0 0 0 0 0 0 1 4 4 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 1 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#NextDiagonal012506

Jan_24_2007 I've got some java play-code multiplying the right-bottom-rooted Pascal's Triangle Matrix now. Here is Pascal's triangle times itself with 10 rows. 1 18 144 672 2016 4032 5376 4608 2304 512 0 1 16 112 448 1120 1792 1792 1024 256 0 0 1 14 84 280 560 672 448 128 0 0 0 1 12 60 160 240 192 64 0 0 0 0 1 10 40 80 80 32 0 0 0 0 0 1 8 24 32 16 0 0 0 0 0 0 1 6 12 8 0 0 0 0 0 0 0 1 4 4 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 AT&T doesn't seem to have these diagonals 8,32,80,160,280,448,672,... -or- 16,80,240,560,1120,2016,... -or- 32,192,672,1792,4032,... -or- 64,448,1792,5376,... (Assuming I didn't lose my place in the row and column alignment) They do have 4,12,24,40,60,84,112,144 = A046092 = 2n(n+1) = http://www.research.att.com/~njas/sequences/A046092 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PTSquare012407

Jan_14_2007 OK. I think I've got a simplistic understanding of this. Random data will have a maximum value. In base 10, the maximum value will start with each digit 1/9 of the time. (No leading 0's assumed) For lower orders of magnitude (numbers with less digits), the starting digit will have 1/9 probability of being each digit. For the ones with the most digits, the potential values are limited by the maximum. To take 1, for example, if the data's maximum starts with 1, 100% of data in the highest order will start with 1. So the approximate expectations for the highest order are: 1 - (1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9)/9 =~ .31433 2 - (1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9)/9 =~ .20321 3 - (1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9)/9 =~ .14766 4 - (1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9)/9 =~ .11063 5 - (1/5 + 1/6 + 1/7 + 1/8 + 1/9)/9 =~ .08285 6 - (1/6 + 1/7 + 1/8 + 1/9)/9 =~ .06063 7 - (1/7 + 1/8 + 1/9)/9 =~ .04211 8 - (1/8 + 1/9)/9 =~ .02623 9 - (1/9)/9 =~ .01235 This oversimplifies it. There's a continuous range of possibilities for each leading digit, depending upon the value of the maximum, but it's close enough to satisfy my curiosity and (I think) demonstrate what's going on. Incidentally, if we pretend that the numbers with less digits than the maximum have leading zeros, then the overall likelihood of encountering a 0 first is over 50% I think. Near 100% if the maximum is in the low 1-somethings of the next place. Near 50% if the max is in the high 9-somethings. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#BenfordCont011406

Jan_12_2007 Here are stats from the first 9 digits for representations of 999.... remlaps@mercury:pts/4:~$ egrep '^\( 1,' replist.txt | wc -l 513 remlaps@mercury:pts/4:~$ egrep '^\( 2,' replist.txt | wc -l 171 remlaps@mercury:pts/4:~$ egrep '^\( 3,' replist.txt | wc -l 88 remlaps@mercury:pts/4:~$ egrep '^\( 4,' replist.txt | wc -l 52 remlaps@mercury:pts/4:~$ egrep '^\( 5,' replist.txt | wc -l 35 remlaps@mercury:pts/4:~$ egrep '^\( 6,' replist.txt | wc -l 25 remlaps@mercury:pts/4:~$ egrep '^\( 7,' replist.txt | wc -l 18 remlaps@mercury:pts/4:~$ egrep '^\( 8,' replist.txt | wc -l 14 remlaps@mercury:pts/4:~$ egrep '^\( 9,' replist.txt | wc -l 13 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MoreStats011206

Jan_12_2007 I just read about Benford's law in "The Golden Ratio" (Mario Livio). Here's wikipedia on Benford's law... http://en.wikipedia.org/wiki/Benford's_law Basically many types of random data are more likely to begin with 1 then any other digits. With "true" random data, I'm willing to bet it doesn't apply. However, with data that is composed of other data, I can almost see how that might be the case. Digit normalization... ie. borrowing/carrying... Let's see if I can describe what I'm thinking. Let's look at base 4 'cause I'm lazy... 0 0 - 0 0 1 - 1 0 2 - 2 0 3 - 3 1 0 - 1 1 1 - 2 1 2 - 3 1 3 - 4 - 10 2 0 - 2 2 1 - 3 2 2 - 4 - 10 2 3 - 5 - 11 3 0 - 3 3 1 - 4 - 10 3 2 - 5 - 11 3 3 - 6 - 12 So if I add 2 1-digit base 4 numbers in base 4: 8 answers start with 1 1 answer starts with 0 3 answers start with 2 4 answers start with 4 50% start with 1. Counterintuitive, but not really surprising. I think any lists of numbers that are created by some form of addition must display this property. Many of the examples Livio gave might be sums... -Populations -Costs -Death tolls Alright, I'm gonna stop being lazy and see what base 10 gives... I don't think I'll type it here. Hold please... So for base 10, I think some of the ratios for sums are: 0 - 1/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 = 1/100 1 - 1/10 + 2/10 + 2/10 + 3/10 + 4/10 + 5/10 + 6/10 + 7/10 + 8/10 + 9/10 = 47/100 2 - 1/10 + 1/10 + 1/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 = 3/100 3 - 1/10 + 1/10 + 1/10 + 1/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 = 4/100 4 - 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 0/10 + 0/10 + 0/10 + 0/10 + 0/10 = 5/100 5 - 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 0/10 + 0/10 + 0/10 + 0/10 = 6/100 ... ... 9 - 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 1/10 + 0/10 = 9/100 So one's are higher than the observed 30.1% so that's not the whole answer, but I'll bet it's part of it. For one thing, we'd have to figure out the percentages for sums with multiple digits. Maybe I'm dense, but the wikipedia explanation doesn't really do it for me. It describes it, but it doesn't explain it. Just for fun, I took a look at all representations of the number 4,000. http://home.ccil.org/~remlaps/javascript/Reps.html Unless I made a mistake, over 50% of them appear start with 1. remlaps@mercury:pts/4:~$ egrep '^\( 1,' replist.txt | wc -l 2025 remlaps@mercury:pts/4:~$ egrep '^\( 2,' replist.txt | wc -l 676 remlaps@mercury:pts/4:~$ egrep '^\( 3,' replist.txt | wc -l 341 remlaps@mercury:pts/4:~$ egrep '^\( 4,' replist.txt | wc -l 204 remlaps@mercury:pts/4:~$ egrep '^\( 5,' replist.txt | wc -l 138 remlaps@mercury:pts/4:~$ egrep '^\( 6,' replist.txt | wc -l 97 remlaps@mercury:pts/4:~$ egrep '^\( 7,' replist.txt | wc -l 73 remlaps@mercury:pts/4:~$ egrep '^\( 8,' replist.txt | wc -l 57 remlaps@mercury:pts/4:~$ egrep '^\( 9,' replist.txt | wc -l 45 remlaps@mercury:pts/4:~$ egrep '^\( 10,' replist.txt | wc -l 38 remlaps@mercury:pts/4:~$ egrep '^\( 11,' replist.txt | wc -l 31 remlaps@mercury:pts/4:~$ egrep '^\( 12,' replist.txt | wc -l 27 That's it for now. Phone's ringing. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#BenfordLaw011207

Jan_10_2007 I haven't had time to look at this any more since before work this morning, but in thinking about it, I think that as N gets bigger, the circle of roots to X^N - X - 1 gets closer to (but never hits) a circle whose ratio is 1, centered at the origin. Real portion of the root on one axis and imaginary portion of the root on the other. http://mathforum.org/library/drmath/view/54842.html reminds me of the long since forgotten general form for a circle: (x-h)^2 + (y-k)^2 = r^2 ;;; Not the same x as above So I'm thinking (most of) the roots of equations of this form approach (x-0)^2 + (y-0)^2 = 1^2 or x^2 + y^2 = 1. Substituting a pair from s^1000 - s - 1 and another pair from s^100 - s - 1, it looks plausible. (+ (expt 0.9609107137273176 2) (expt 0.27931781145484286 2)) 1.0013678395518661 (+ (expt 0.9570905179703053 2) (expt 0.31265467963134397 2)) 1.0137752082840457 I'm speculating that there are no rationals in any of the roots, real or imaginary. Also, it occurs to me, this is a tenuous link between phi and pi. (kind of like my uncle's step-son's wife's friend's boss ; -) Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PhiFormulaCircleRoot011007

Jan_10_2007 According to http://www.eecircle.com/applets/003/003.html Most of the roots of the X^n - x - 1 equations look like they make a circle around the origin with a radius of 1 (although phi and the other ones I listed yesterday are not part of the circle). I wonder how unusual that is. My computer's locked up calculating s^1000 - x - 1 now, so I'm not sure exactly what constructs the circle. Just the real parts of the roots I guess. I'll have to look at it again later. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#CircleRoots011006

Jan_09_2007 According to http://monet.physik.unibas.ch/~elmer/pendulum/polyroot.htm Roots of x^3 - x - 1 (x^3 == x+1) are: -0.6624 -0.5623i -0.6624 +0.5623i 1.3247 I bet the Real is irrational. I'm sure it's rounded. I got 1.324717958 for the Real one by trial and error. I wonder if there's a way to describe that number exactly and succinctly. So if we call that number N and apply Pascal's triangle (binomial theorem I guess), N^6 should be N^2 + 2N + 1 and N^9 should be N3 + 3N^2 + 3N + 1. (setq N 1.324717958) 1.324717958 (expt N 6) 5.404313599222967 (+ (expt N 2) (* N 2) 1) 5.4043135842476895 (expt N 9) 12.563504892183897 (+ (expt N 3) (* (expt N 2) 3) (* N 3) 1) 12.563504839963949 Close enough. Useless, but fun. Ignoring imaginaries, here's a summary of what that web page tells me about roots of this format. x^2 - x - 1 positive root = phi ;(1.6180...) x^3 - x - 1 positive root = 1.324717958 x^4 - x - 1 positive root = 1.2207 x^5 - x - 1 positive root = 1.1673 x^2 - x - 1 negative root = (phi - 1) * - 1 ;(-0.6180...) x^3 - x - 1 no negative (REAL) root x^4 - x - 1 negative root = -0.7245 x^5 - x - 1 no negative (REAL) root Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#XcubedIsXPlus1-010907

Jan_09_2007 Quadratic formula: (-b +/- sqrt(b^2 - 4ac))/2a Start with: x^2 = x+1 Convert from terms of X to terms of X+1 100 = 11 1,-2,1 = 1,0 Back to polynomails x^2 - 2x + 1 = x x^2 - 3x + 1 = 0 Find roots. (3 +/- sqrt(3^2 - 4))/2 = roots Back substitute. (3 + (sqrt 5)) / 2 = x+1 (phi + 1) (3 - (sqrt 5)) / 2 = x+1 (some other number + 1) Actual values. (- (/ (+ 3 (sqrt 5)) 2) 1) ;; phi 1.618033988749895 (- (/ (- 3 (sqrt 5)) 2) 1) ;; some other number -0.6180339887498949 Computer rounding error, but close enough. (+ -0.6180339887498949 1) 0.3819660112501051 (* -0.6180339887498949 -0.6180339887498949) 0.3819660112501052 So besides having the exact same digits as phi to the right of the decimal place, what is that number? Anything? some_other_number + 1 = some_other_number^2 = 1/phi^2. (/ 1 (expt phi 2)) 0.38196601125010515 Which, incidentally, is "the phi-series mean velocity for the synodic difference cycle between Jupiter and Saturn" and also "the mean distance of Mercury" and also "the mean synodic period between the latter and Venus" http://www.spirasolaris.ca/sbb4f.html Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#Xplus1isXSquared010907

Jan_08_2007 Here are some more, similarly related (coefficients for) polynomials... 0,0,1,1,1 0,0,1,3,3 0,0,1,5,7 0,0,1,7,13 0,0,1,9,21 0,0,1,11,31 0,1,1,1,1 0,1,4,6,4 0,1,7,17,15 0,1,10,34,40 0,1,13,57,85 1,1,1,1,1 1,5,10,10,5 1,9,31,49,31 1,13,64,142,121 1,17,109,313,341 1,21,166,586,781 1,25,235,985,1555 I think maybe I'm tail-chasing. Interesting that some of those rows show up in AT&T's sequences in triangles related to Pascal's triangle though. For example- 1,13,64,142,121 http://www.research.att.com/~njas/sequences/A119673 That one just showed up in June of 2006 if I'm interpreting right. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#MoreRelations010806

Jan_08_2007 Just for fun... Phi^2 = Phi+1 100_Phi = 11_Phi => 1 0 0 [1 2 1 0 1 1 0 0 1] = 1 2 1 => 121_(Phi-1) 1 2 1 [1 2 1 0 1 1 0 0 1] = 1 4 4 => 144_(Phi-1) 1 1 [1 1 0 1] = 1 2 => 12_(Phi-1) 1 2 [1 1 0 1] = 1 3 => 13_(Phi-1) (+ (* (- phi 1) (- phi 1)) (* 2 (- phi 1)) 1) ; 1 2 1 2.618033988749895 (+ (- phi 1) 2) ; 1 2 2.618033988749895 (+ (* (- phi 2) (- phi 2)) (* 4 (- phi 2)) 4) ; 1 4 4 2.618033988749895 (+ (- phi 2) 3) ; 1 3 2.618033988749895 But none of those are legal digits, so it's an abuse of notation. I just wanted to see the relationships though. So that really means- Phi^2 (100) = 1(Phi-1)^2 + 2(Phi-1) + 1 ;(121) = 1(Phi-2)^2 + 4(Phi-2) + 4 ; (144) = 1(Phi-3)^2 + 6(Phi-3) + 9 ; (169) = 1(Phi-4)^2 + 8(Phi-4) + 16 ; (196) = 1(Phi-5)^2 + 10(Phi-5) + 25 ; (225) ... ... = Phi+1 (11) ; Definitely stating the obvious after here... = (Phi-1) + 2 (12) = (Phi-2) + 3 (13) = (Phi-3) + 4 (14) ... I've been wondering about something like "canonical forms" of polynomials too. It's interesting that the final terms, without normalization, are perfect squares. 196 "comes from" 10^2 + 8(10) + 16. It could just as easily be 1 + 70 + 26 or 1 + 90 + 6. Is there anything special about the form of the polynomial derived as above? Is that a fundamental form of some kind? I don't really know what I mean. This needs more thought and more time. Just the start of an idea occupying my thoughts today. Whatever I mean, related polynomial forms might be: 1,0,0 1,2,1 1,4,4 1,6,9 1,8,16, 1,10,25 1,12,36 -and- 1,0,0,0 1,3,3,1 1,6,12,8 1,9,27,27 1,12,48,64 -and- 1,0,0,0,0 1,4,6,4,1 1,8,24,32,16 1,12,54,108,81 1,16,96,256,256 1,20,150,500,625 Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#FunWithPhi010806

Jan_07_2007 So I'm reading my new Scientific American book about Phi (The Golden Ratio). It mentioned that Phi + 1 = Phi^2. Of course, that jumped out at me. It seems we can find Pascal's triangle in even powers of phi or we can use Pascal's triangle to find even power's of phi. Phi^2 = (Phi + 1) // { 1 } Phi^4 = (Phi + 1)^2 = Phi^2 + 2.Phi + 1 // { 1, 2, 1} Phi^6 = (Phi + 1)^3 = Phi^3 + 3.Phi^2 + 3.Phi + 1 // {1, 3, 3, 1} Phi^8 = (Phi + 1)^4 = Phi^4 + 4.Phi^3 + 6.Phi^2 + 4.Phi + 1 // {1, 4, 6, 4, 1} ... That's all obvious, but it surprised me anyway. Here's some elisp demonstrating the relationship for phi^8. (setq phi (/ (+ 1 (sqrt 5)) 2)) 1.618033988749895 (expt phi 8) 46.978713763747805 (+ (expt phi 4) (* 4 (expt phi 3)) (* 6 (expt phi 2)) (* 4 phi) 1) 46.97871376374779 I hope those last digits are wrong due to a round-off error inside the computer. I think they must be 'cause here's a third answer... (expt (expt phi 2) 4) 46.9787137637478 And here's a match for Phi^8 (expt (expt phi 4) 2) 46.978713763747805 And here's a match for the Pascal's triangle answer... (expt (expt (expt phi 2) 2) 2) 46.97871376374779 I'm convinced. Computer precision problem. Link for this entry: http://home.ccil.org/~remlaps/weblog_2007/mathematics_index.html#PhiFourth010707