Let's talk about Number

Anyone who has been around Maths for awhile will have come across some numbers that have special properties. 42 is one of those numbers, but I’ve long ago forgotten how it is so. Anyone who can fill us in is welcome to have a go.

If you know of some special numbers, add them so this topic.

Today I learned about Narcissistic Numbers which are composed of digits that when raised to the power of the number of digits, and then added together will arrive at the same number. The example given was 8208. Being a curious sort, I had to test that…

>>> from math import log10, floor
>>> x = 8208
>>> n = floor(log10(x)) + 1
>>> y = 0
>>> while x > 0:
	y += (x % 10) ** n
	x //= 10

	
>>> y
8208
>>> 

Looking forward to any interesting numbers you’ve come across to let’s keep this topic growing!


One suspects this is not going to light many fires, but my own faith says it will start one or two. Now that we know the four digit number that fits this scenario we are left with the question of whether there are two and three digit numbers that act the same. Extending beyond four digit numbers will follow, as curiosity goes.

Apparently there are 88 such known numbers that satisfy this construct. The good news is that they are all less than, 10^39.

3 Likes

One has always held that exponent laws (including log) and calculus should be introduced in Grade 7. Right at the beginning of junior high maths. What an eye opener it would be at a crucial time in the learning curve. From there on the expectations would be from the learners, not the teachers.

1 Like

Here is the Wiki page on 42, and it has some very interesting elements. I think 42, in old programming, was the number representing *, which (as some of you may know), means everything.

2 Likes

Proof of concept…

from math import log10, floor
def nn(n):
    a = 10 ** (n - 1) + 1
    b = 10 ** n
    print (a, b)
    for i in range(a, b):
        x = i
        y = 0
        while x > 0:
            y += (x % 10) ** n
            x //= 10
        if i == y: print (i, y)

output

>>> nn(2)
>>> 11 100
>>> nn(3)
101 1000
153 153
370 370
371 371
407 407
>>> nn(4)
1001 10000
1634 1634
8208 8208
9474 9474
>>> nn(5)
10001 100000
54748 54748
92727 92727
93084 93084
>>> nn(6)
100001 1000000
548834 548834
>>> nn(7)
1000001 10000000
1741725 1741725
4210818 4210818
9800817 9800817
9926315 9926315
>>> 

The last one (n==7) took about 10 seconds. One expects it will take a long time to get to n==39. Something for a super computer to chew through. We’ve found the first 15 of 88.

One speedup I can see is to store the results of (0…9) ** n in a dictionary that way we only have to calculate once and lookup these values instead of doing a calculation for every digit of every num in the range.
We will still hit a wall pretty quickly and might not even get n=8 in a reasonable time still but it will help.
Something like

from math import log10, floor
def nn(n):
    a = 10 ** (n - 1) + 1
    b = 10 ** n
    nums = range(10)
    exponents = {x:x**n for x in nums}
    print (a, b)
    for i in range(a, b):
        x = i
        y = 0
        while x > 0:
            y += exponents[x % 10]
            x //= 10
        #print ((i, y), end=", ")
        if i == y: print (i, y)
1 Like

took about two minutes to get n(8) with the updated code

10000001 100000000

24678050 24678050

24678051 24678051

88593477 88593477

It took about half the time to do nn(7).

from math import log10, floor

def nn(n):
    a = 10 ** (n - 1) + 1
    b = 10 ** n
    print (a, b)
    d = {x: x ** n for x in range(10)}
    for i in range(a, b):
        x = i
        y = 0
        while x > 0:
            y += d[x % 10]
            x //= 10
        if i == y: print (i, y)

Edit.

The calculation mode took 32 seconds to do nn(7). The dictionary mode took 12 seconds. That’s a substantial improvement. Thanks @fight_dragons for chipping in.

My system is a 2013 A10 with 16 GB Ram. Python 3.8


Edit

My machine is obviously not as fast as today’s machines. The 8 digit call took 5 and a half minutes to complete.

When thinking how this could be done with binary, given that bitwise operators are 32 bit (still?) we would have to interleave each order of magnitude to handle the larger numbers. We couldn’t get all the way to 10^39, but close. Our limit would be 128 bits. That gives us four interleaves. We could then go through all the permutations. Still, a tonne of work but I’m betting it would be the fastest.

I’ve made another improvement.
Consider the numbers 135,153,315,351,513,531 - they all have the same sum
If we could filter out all these combination numbers we could reduce the amount of calculations we need to do enormously. For example when n=2 we only have 45 numbers to check instead of 90
when n = 7 we go from 9000000 sums to calculate to just 11440 sums to calculate

That’s all a bit math-y and I have not done a great job explaining but heres the code

from itertools import combinations_with_replacement


def nn(n):
    a = 10 ** (n - 1) + 1
    b = 10 ** n
    print(a, b)

    nums = [x for x in range(10)]
    d = {x: x ** n for x in range(10)}
    nums_to_check = list(combinations_with_replacement(nums, n))
    nums_to_check = [int(''.join(map(str, idx))) for idx in nums_to_check]
    z = [sum(map(lambda x: d[int(x)], str(x))) for x in nums_to_check]
    for num in z:
        if num in range(a, b) and sum(map(lambda x: d[int(x)], str(num))) == num:
            print(num)

It’s as messy as the explanation but it ran nn(7) in a tenth of a second nn(13) takes about 5 seconds
My machine is a 2012 mbp with 4gb ram python 3.8
I’m excited to see your results!

1 Like

Holy cow! So my notion of working with permutations had some validity. Going to give your code a run and see what happens (just so).

We could see some symmetry just in the early outputs. You’ve made that perfectly clear. Brilliant work.

Edit

Yeah, nn(13) took about 5 seconds. So we should be able to do nn(14) in about a minute. Off to try…

15 seconds. Again, brilliant!

1 Like
>>> nn(19)
1000000000000000001 10000000000000000000
1517841543307505039
3289582984443187032
4929273885928088826
4498128791164624869
>>> 

One minute, fifty five. Amazing.

1 Like

Didn’t make a difference on time, but adding to conciseness…

    nums = [*range(10)]
    d = {x: x ** n for x in nums}

I cleaned up the code some more, there were some type conversions where there didn’t need to be so I got a negligible amount of speed out of it. Thanks for making this post, you definitely got at least one fire going. I had a lot of fun digging deep into some numbers and watching the code evolve.

def nn(n):
    a = 10 ** (n - 1) + 1
    b = 10 ** n
    print(a, b)

    nums = [*range(10)]
    d = {x: x ** n for x in nums}
    nums_to_check = list(combinations_with_replacement(nums, n))
    nums_to_check = [(''.join(map(str, num))) for num in nums_to_check]
    nums_to_check = [sum(map(lambda x: d[int(x)], num)) for num in nums_to_check]
    for num in nums_to_check:
        if num in range(a, b) and sum(map(lambda x: d[int(x)], str(num))) == num:
            print(num)
1 Like

Hey, I’m glad you enjoy this topic and have taken a dive into it. Fear of Maths keeps so many learners from taking a deep dive into the study of Number (which they mistakenly equate to Maths). Given that math is something that comes so naturally, the fear of it is like being afraid of the dark. An irrational fear (no pun intended), to be sure.

I’m terrible at math once it starts getting overly esoteric, but it is still interesting and I at least can tell when I’m in over my head. Wouldn’t be able to tell that if I didn’t at least jump in.

The first iteration of your code,

>>> nn(12)
100000000001 1000000000000
3.355858087539673

The latest iteration,

>>> nn(12)
100000000001 1000000000000
3.3543307781219482
>>> 

For timing I used the datetime.datetime.timestamp() method.

    from datetime import datetime as dt
    ...
    ta = dt.timestamp()
    ...
    tz = dt.timestamp()
    print (tz - ta)

Aside

One question I have,

if num in range(a, b) ...

Is there any chance that num will not be in the range?

yes, at n = 3 our range is 101 - 1000 consider 999 its sum 9^3 + 9^3 + 9^3 = 2187
or 111 - 1^3 + 1^3 + 1^3 = 3
Now the choice is between the range check or computing 2^3 + 1^3 + 8^3 + 7^3 which we know will always be false anyway. I’m assuming that the range check will be faster so it went on the left hand of the ‘and’ statement so we can short circuit the out of ranges.

I think this could be worked around - however
nums_to_check = list(combinations_with_replacement(nums, n))
This line does the heavy lifting of getting the unique integer digit sets(just 135, not its permutations ) for us. Sadly it does it for the range 0-b not a-b. We could reinvent the wheel in a big way to save some time. Let’s measure how much time
The list size of the integer digit sets ‘nums_to_check’ is ( n+9 choose 9)
At n = 3 there are (12 choose 9) = 220 sets
At n = 2 there are (11 choose 9) = 55 of these sets
As it stands we are overpopulating our list and doing the extra bounds check on 55 extra sets.

Luckily we know that n=39 is our highest possible n (theres math to prove this as well lol)
at n= 39 there are 1677106640 sets
at n= 38 there are 1362649145 sets
Only need 314,457,495 while we use 1677106640 sets
About 5.33 times the work we need to do.

That’s the last big bottle neck I see here. If we could reduce the size of nums_to_check we could save a lot of those conditional checks later.

1 Like

Yeah, now you mention, it should have been obvious.

I got a slight boost in speed by leaving it as the iterator and letting the list comprehension cover the conversion.

nums_to_check = combinations_with_replacement(nums, n)
>>> nn(12)
100000000001 1000000000000
3.3543307781219482
>>> 
= RESTART: C:/../Scripts/narcissistic_number.py
>>> nn(12)
100000000001 1000000000000
3.235592842102051
>>> 

Good catch - that cast isn’t necessary.

Had to take a second look when you wrote, (n + 9)C9. But just to see for myself,

>>> len([*combinations_with_replacement(range(10), 3)])
220
>>> from math import factorial as f
>>> f(12) / (f(12-9) * f(9))
220.0
>>> 

Told ya I did some digging haha. You owe me if you ever win any bar bets with that one.

1 Like

I’ve forgotten all the little tricks that used to get my glass refilled. 1089 comes to mind, that one paid off a lot. The cube of a 3-digit number was impressive but I’ve long ago forgotten the mental algorithm for that one.

Given only 3 seconds can you multiply any three digit number by 7, 11 and 13? (Don’t give it away if you can.)

This topic is about Number in all its fashion and quirkiness. Let’s keep it going.

Owing that our combination object is consumed, we can give it its own variable. The result is now the sample size we’re working with from here on out.

from itertools import combinations_with_replacement
from datetime import datetime as dt

def nn(n):
    ta = dt.now().timestamp()
    a, b = 10 ** (n - 1) + 1, 10 ** n
    print(a, b)
    nums = [*range(10)]
    d = {x: x ** n for x in nums}
    nCr = combinations_with_replacement(nums, n)
    sample = [(''.join(map(str, num))) for num in nCr]
    sample = [sum(map(lambda x: d[int(x)], num)) for num in sample]
    for num in sample:
        if num in range(a, b) and sum(map(lambda x: d[int(x)], str(num))) == num:
            print(num)
    tz = dt.now().timestamp()
    print (tz-ta)