[math-fun] 2015 is palindromic in binary
This would have been more appropriate about 11 months ago. 2015 = 11111011111 in base 2. When's the next time that happens? -- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming. On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
On 2015-12-08 13:01, Tom Rokicki wrote:
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming.
I think the answer for a general string (other than all 1's) is that the next binary palindrome occurs when the "middlemost" pair of 0's (middle single bit, when the middle bit is 0) flip from 0 to 1. Otherwise, if the binary number is 2^n - 1, then the next palindrome is 2^n+1
On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
--
-- http://cube20.org/ [1] -- [ [2]Golly link suppressed; ask me why] --
Links: ------ [1] http://cube20.org/ [2] http://golly.sf.net/
Mike's answer is correct when the middle bit _is_ a 0, or when the current palindrome is all 1's. But 10101 -> 11011 is a transition not accounted for in his rule. On Tue, Dec 8, 2015 at 4:15 PM, Michael Greenwald <greenwald@cis.upenn.edu> wrote:
On 2015-12-08 13:01, Tom Rokicki wrote:
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming.
I think the answer for a general string (other than all 1's) is that the next binary palindrome occurs when the "middlemost" pair of 0's (middle single bit, when the middle bit is 0) flip from 0 to 1. Otherwise, if the binary number is 2^n - 1, then the next palindrome is 2^n+1
On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
--
-- http://cube20.org/ [1] -- [ [2]Golly link suppressed; ask me why] --
Links: ------ [1] http://cube20.org/ [2] http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's a (possibly null) block of 1s between the "middlemost pair" of 0s. When you flip that middlemost pair, zero the block of 1s. Alternative statement: flip the middlemost pair of 0s, and everything in between. --Rich -----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Tuesday, December 08, 2015 2:47 PM To: greenwald@cis.upenn.edu; math-fun Subject: [EXTERNAL] Re: [math-fun] 2015 is palindromic in binary Mike's answer is correct when the middle bit _is_ a 0, or when the current palindrome is all 1's. But 10101 -> 11011 is a transition not accounted for in his rule. On Tue, Dec 8, 2015 at 4:15 PM, Michael Greenwald <greenwald@cis.upenn.edu> wrote:
On 2015-12-08 13:01, Tom Rokicki wrote:
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming.
I think the answer for a general string (other than all 1's) is that the next binary palindrome occurs when the "middlemost" pair of 0's (middle single bit, when the middle bit is 0) flip from 0 to 1. Otherwise, if the binary number is 2^n - 1, then the next palindrome is 2^n+1
On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
--
-- http://cube20.org/ [1] -- [ [2]Golly link suppressed; ask me why] --
Links: ------ [1] http://cube20.org/ [2] http://golly.sf.net/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 2015-12-08 13:46, Allan Wechsler wrote:
Mike's answer is correct when the middle bit _is_ a 0, or when the current palindrome is all 1's. But 10101 -> 11011 is a transition not accounted for in his rule.
Ouch. You are right -- my rule is wrong, and needs amendment. The central string of "1"'s surrounded by the "middlemost" pair of 0's must all be changed to 0's, too.
On Tue, Dec 8, 2015 at 4:15 PM, Michael Greenwald <greenwald@cis.upenn.edu> wrote:
On 2015-12-08 13:01, Tom Rokicki wrote:
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming.
I think the answer for a general string (other than all 1's) is that the next binary palindrome occurs when the "middlemost" pair of 0's (middle single bit, when the middle bit is 0) flip from 0 to 1. Otherwise, if the binary number is 2^n - 1, then the next palindrome is 2^n+1
On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
--
-- http://cube20.org/ [1] [1] -- [ [2]Golly link suppressed; ask me why] --
Links: ------ [1] http://cube20.org/ [1] [2] http://golly.sf.net/ [2]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun [3]
Links: ------ [1] http://cube20.org/ [2] http://golly.sf.net/ [3] https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 2015-12-08 14:03, Michael Greenwald wrote:
On 2015-12-08 13:46, Allan Wechsler wrote:
Mike's answer is correct when the middle bit _is_ a 0, or when the current palindrome is all 1's. But 10101 -> 11011 is a transition not accounted for in his rule.
Ouch. You are right -- my rule is wrong, and needs amendment. The central string of "1"'s surrounded by the "middlemost" pair of 0's must all be changed to 0's, too.
Not sure why anyone would care, but while waiting for one of my kids to finish ultimate frisbee practice, I wrote a program to return the nth base 2 palindrome directly (written in python, because that was what was on her laptop), without computing the n-1 predecessors [If you were wondering, the 123948568686823355th base 2 palindrome is 3739138785482516278676171216476701, or: '1011100001011010100100010000011011111111000001111011101111011101111000001111111101100000100010010101101000011101' ] Here's the code: import math import numbers # There's probably a better way to do this in python, but... def nbits( n ): # treat '0' as the empty (0-length) string, to avoid special # cases when we recurse if( n == 0 ): return 0 return int( math.log( n, 2 )) + 1 def palindrome( n, even ): """make a palindrome out of a k-bit number n. If even is False, then create a number with an odd number of bits (2k - 1), by keeping the rightmost bit of n as the center, and reversing all the other k-1 bits of n. If even is True, create the 2k bit palindrome by reversing all the bits of n. In both cases, concatenate the original n with the reversed bits. """ assert n > 0 or ( n == 0 and even ) offset = 0 if even else 1 k = nbits( n ) return ( n << ( k - offset )) | ( reversal( n >> offset , k - offset )) def nthPalindrome( n ): assert( isinstance( n, numbers.Integral )) assert( n >= 0 ) if( n <= 1 ): return 0 border = 1 << ( nbits( n ) - 2 ) return palindrome( border + ( n & ( border - 1 )), bool( n & border )) # code for reversal( n, k ) # memo-ize reversal of numbers mod 2^precomputedBits _rev = {} _precomputedBits = 8 _precomputed = 1 << _precomputedBits def reversal1( n, k ): """return the reversal of n, as a k-bit string, trying to take advantage of cached, reversed, substrings. If no precomputed reversal is available, compute it recursively.""" if( k <= 1 ): return n if( k <= _precomputedBits ): key = int( n << ( _precomputedBits - k )) val = _rev.get( key, None ) if val is None: val = int( reverse2( n, k )) _rev[ key ] = val return val # Avoid some recursion for sparse numbers... k is wide, but # n itself is small (and may be precomputed). if( n < _precomputed ): return reverse2( n, _precomputedBits ) << ( k - _precomputedBits ) return reverse2( n, k ) def reverse2( n, k ): """Compute the reverse of the bits of n as a k-bit string by reversing the lower 'half' of the bits and concatenating with the reverse of the upper 'half' of the bits""" half = k/2 leftover = k - half return ( reversal1( n>>half, leftover ) | ( reversal1( n & (( 1 << half ) - 1 ), half ) << leftover )) def reversal( n, k ): """reverse the bits of n, treated as a k-bit string (k tells you how many leading zeroes to include)""" assert( k >= 0 ) assert( n >= 0 ) assert( isinstance( n, numbers.Integral )) assert( isinstance( k, int )) assert( n < ( 1 << k )) return reversal1( n, k )
On Tue, Dec 8, 2015 at 4:15 PM, Michael Greenwald <greenwald@cis.upenn.edu> wrote:
On 2015-12-08 13:01, Tom Rokicki wrote:
Looks good to me! We now return you to your regularly scheduled WDS/rwg programming.
I think the answer for a general string (other than all 1's) is that the next binary palindrome occurs when the "middlemost" pair of 0's (middle single bit, when the middle bit is 0) flip from 0 to 1. Otherwise, if the binary number is 2^n - 1, then the next palindrome is 2^n+1
On Tue, Dec 8, 2015 at 12:47 PM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
On 2015-12-08 12:29, Tom Rokicki wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2. When's the next time that happens?
Isn't it 2047? (If the last 5 bits were anything other than 11111, the high order bits would have to change, too, and that could take a bunch more years).
--
-- http://cube20.org/ [1] [1] -- [ [2]Golly link suppressed; ask me why] --
Links: ------ [1] http://cube20.org/ [1] [2] http://golly.sf.net/ [2]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun [3]
Links: ------ [1] http://cube20.org/ [2] http://golly.sf.net/ [3] https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I mentioned this in New Year’s greetings to my friend and colleague Chris Henley, who sadly passed away on June 29. -Veit
On Dec 8, 2015, at 3:29 PM, Tom Rokicki <rokicki@gmail.com> wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2.
In base 10, what you need is https://oeis.org/A262038, the palindromic ceiling function (next pal). In base 2 it is A175298. The news about Chris Henley is a shock. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Tue, Dec 8, 2015 at 5:22 PM, Veit Elser <ve10@cornell.edu> wrote:
I mentioned this in New Year’s greetings to my friend and colleague Chris Henley, who sadly passed away on June 29.
-Veit
On Dec 8, 2015, at 3:29 PM, Tom Rokicki <rokicki@gmail.com> wrote:
This would have been more appropriate about 11 months ago.
2015 = 11111011111 in base 2.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Allan Wechsler -
Michael Greenwald -
Michael Greenwald -
Neil Sloane -
Schroeppel, Richard -
Tom Rokicki -
Veit Elser