Find numbers that are palindromic in consecutive number bases

Question

I want to generate numbers which are palindromic in three or more consecutive number bases in the most optimal, fastest way (up to some range). I do not count trivial one digit palindromes.

(When I say 3 or more, I mean 3 and 4, as it is not known if a solution for 4 or more bases exists)

I'm basically generating palindromes in number base \$b\,ドル and then converting and checking whether it is also palindromic in \$b+1, b+2, \dots\$

Are there any ways to noticeably speed up my code?

---

# Converts any number n to any base b (*), Source: [1]
# https://stackoverflow.com/a/28666223/5821790
def numberToBase(n, b):
 if n == 0:
 return [0]
 digits = []
 while n:
 digits.append(int(n % b))
 n //= b
 return digits[::-1]
# Generates palindromes in base b (*), Source: [2]
# https://math.stackexchange.com/q/2494909
def palgen(b):
 i = 1
 while True:
 ii = b * i
 r = range(i, ii)
 for j in r:
 s = numberToBase(j, b)
 yield s + s[-2::-1]
 for j in r:
 s = numberToBase(j, b)
 yield s + s[::-1]
 i = ii
# Checks if the list is palindromic, Source: [3]
# https://stackoverflow.com/a/30340347/5821790
def isPalindrome(s):
 if len(s) <= 1:
 return True
 return s[0] == s[-1] and isPalindrome(s[1:-1])
# converts number in base b (*) to integer
def listToInt(digitList, base):
 l = len(digitList)
 value = 0
 for i, val in enumerate(digitList):
 value += val*base**(l-i-1)
 return value
# returns current time
def getTime():
 return strftime("( %H:%M:%S )", gmtime())
###################################################################
# Searches for numbers palindromic in 3 or more consecutive bases #
###################################################################
from time import gmtime, strftime
from math import sqrt, floor
bound = 10**8 # numbers up to
baseBound = floor(sqrt(bound)) # bases up to (bound, can be improved)
print(getTime(), "Starting with:" ,baseBound, bound)
for b in range(2, baseBound):
 for i, s in enumerate(palgen(b), 1):
 # convert palindrome s_b to integer x and check if out of bound
 x = listToInt(s, b)
 if (x > bound): break
 if (len(s) > 1): # one digit palindromes do not count (trivial)
 # checks if the palindrome x is also palindromic in more bases
 if (isPalindrome(numberToBase(x, b+1))):
 if (isPalindrome(numberToBase(x, b+2))):
 print(getTime(), b, x, len(s))
 if (isPalindrome(numberToBase(x, b+3))):
 print(b, x, len(s), "*** AT LEAST FOUR IN A ROW ***")

What are some things here that can be improved, and how, following good practice?

(Beside mathematical aspects which include the bound above which no more examples are found, the fact that only odd digit length palindromes form consecutive triples, and the facts that some examples follow a pattern that can be generated.)

Sources: [1] [2] [3]

Outputs: [10^9, ~ 3 hours: 1200 bases] and [10^12, ~ 3 hours: 100 bases]

• user1149: stackoverflow.com/questions/931092/reverse-a-string-in-python may be a faster way to reverse strings (and thus check palindromity). You might also consider generating palindromes in the highest base first and then looking at b-1, b-2 etc. You might also be able to use "mod" to discard multiples of a given base (depending on how you treat strings that end in "0").
• Laurent LAPORTE: Avoid to redefine a built-in function like eval.
• Vepir: @BarryCarter My palindromes are stored and handled as lists of integers, not exactly strings, but I can still apply the same thing on it: and turns out my recursive function seems to be roughly the same speed compared to something like s == s[::-1] , If I'm not mistaken? Also, I'm not sure how you meant to discard duplicates exactly?
• Vepir: @LaurentLAPORTE Renamed it to listToInt
• Laurent LAPORTE: @Vepir It is recommended to respect PEP8 naming convention, so I prefer: list_to_int.

Answer 1

A small performance improvement is possible in the listToInt function, by using multiplications only instead of exponentiation (which is Horner's method):

# converts number in base b list representation to integer
def listToInt(digitList, base):
 value = 0
 for val in digitList:
 value = value * base + val
 return value

On my computer this reduced the time to compute the results for \$ b = 1270, \ldots, 1286 \$ from 130 to 101 seconds.

• Vepir: I'll be accepting this as there seems to be no other improvements lying near by.

Answer 2

This numberToBase function can be defined as: def numberToBase(n, b): return int(str(n), b)) Also as stated in comment isPalindrom can be defined as: def isPalindrom(s): return s == s[::-1] This may speed it up a bit.

• Vepir: You didn't even read what my numberToBase does; your definition of it seems to do the reverse, but not even that really as perhaps you also aren't aware that int(str, int) only has range for number bases in [2,36], am I not mistaken?