Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n). There are 120 reversible numbers below one-thousand.
How many reversible numbers are there below one-billion (10^9)?
Meta thinking about how to approach the problem:
Kinds of approaches: Mathematical -- there may be a "formula" or other obvious way to find the answer. E.g. there are always 120 reversible numbers per 1000, so there are 120,000,000 below 1 billion (I'm sure this isn't actually true, just an example Programming Brute force. We can simply check all numbers below one billion. I think that this computation would be fast enough to run in roughly 10 minutes, so I think this is actually a pretty promising approach Something more clever. Maybe start w/ the "answers" (all numbers below, I think, 2 billion that are made up of only odd digits), and see whether they can be made by adding a number less than one billion to its reverse This doesn't actually seem promising to me
Task summary:
Stack of tasks:
Work in progress: 1)
n = 100 ## 10e9
for i in range(n):
digits = str(i)
reverse_digits = digits[::-1]
# continue here
Task summary:
Stack of tasks:
Work in progress: 1)
def stringsToSum(first, second):
return first + second
n = 20 ## 10e9
for i in range(n):
digits = str(i)
reverse_digits = digits[::-1]
sum = stringsToSum(digits, reverse_digits)
is_even = int(sum) % 2 == 0
print is_even
#continue here
Task summary:
Stack of tasks:
Work in progress:
from multiprocessing.dummy import Pool as ThreadPool
def stringsToSum(first, second):
return first + second
def is_reversible(n):
digits = str(n)
reverse_digits = digits[::-1]
sum = stringsToSum(digits, reverse_digits)
is_odd = lambda digit: int(digit) % 2 != 0
return all(map(is_odd, sum))
n = 1000000
pool = ThreadPool(4)
result = pool.map(is_reversible, range(n))
print len(filter(lambda x: x, result))
This currently seems to be too slow. Not sure if additional parallelization will help. If not, maybe consider running for various smaller values of n and see if we can figure out any pattern
previous person's implementation seems incorrect: it gives 155 reversible numbers below 1000
idea for optimizations: if any pair of digits are both even or both odd, can skip
Task summary:
Stack of tasks:
Work in progress:
from multiprocessing.dummy import Pool as ThreadPool
def stringsToSum(first, second):
return first + second
def is_reversible(n):
digits = str(n)
reverse_digits = digits[::-1]
sum = stringsToSum(digits, reverse_digits)
is_odd = lambda digit: int(digit) % 2 != 0
return all(map(is_odd, sum))
n = 1000000
pool = ThreadPool(4)
result = pool.map(is_reversible, range(n))
print len(filter(lambda x: x, result))
This currently seems to be too slow. Not sure if additional parallelization will help. If not, maybe consider running for various smaller values of n and see if we can figure out any pattern
To upcoming players: try to timestamp your notes as well as indicating your identity, in order to not be confused as to whether previous notes were from one or several players. These notes are from Aug 6 and one person: The approach of the previous player seems fine. I didn’t have time to get into the nitty gritty much. The code won’t compile however, so I had to integrate the last filter to a list.
from multiprocessing.dummy import Pool as ThreadPool
def stringsToSum(first, second):
return first + second
def is_reversible(n):
digits = str(n)
reverse_digits = digits[::-1]
sum = stringsToSum(digits, reverse_digits)
is_odd = lambda digit: int(digit) % 2 != 0
return all(map(is_odd, sum))
n = 1000000
pool = ThreadPool(4)
result = pool.map(is_reversible, range(n))
print(len(list(filter(lambda x: x, result))))
One billion isn’t that big, you can just check them all if each check is fast Yeah, I think you can just do it (assuming a fast enough language) I’m going to just try doing it brute force in go I think this suffices for reverse:
func reverse(n int) int {
result := 0
for n > 0 {
result = 10*result + n%10
n /= 10
}
return result
}
(12:17:47 AM) Then reversible is fairly straightforward too... (12:18:42 AM) Does this work?
func reversible(n int) bool {
sum := n + reverse(n)
for sum > 0 {
if (sum % 10) % 2 == 0 {
return false
}
sum /= 10
}
return true
}
This gives me 125 reversible numbers below 1000… what? Is there some leading zeros thing going on, I think that’s what’s it. A reversible number can’t be divisible by 10! Great, checking for that gives us 120 as expected. (12:22:12 AM) OK, running up to 1 billion… hopefully this will finish in time Code: package main
import "fmt"
func reverse(n int) int {
result := 0
for n > 0 {
result = 10*result + n%10
n /= 10
}
return result
}
func reversible(n int) bool {
if n%10 == 0 {
return false
}
sum := n + reverse(n)
for sum > 0 {
if (sum%10)%2 == 0 {
return false
}
sum /= 10
}
return true
}
func main() {
count := 0
for i := 1; i < 1000000000; i++ {
if reversible(i) {
count++
}
}
fmt.Println(count)
}
Answer: 608720 (took 30 seconds to run) (12:22:49 AM) done