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