Coding: Bring the Noise

%26lt;0011 Em

Takkuso’s Cycles

leave a comment »

I saw an interesting post on /r/math today, and decided to write a small script to play around with it.

  1. Pick a positive integer, i
  2. Find the magnitude, m, of the difference between i and i’s reverse, j
  3. Repeat step 2 using m; you will eventually hit either 0 or a special number.

The special number is 21, followed by min(0, log10(i)-4) 9s, then 78.

A quick table:

# of digits Special number
4 2178
5 21978
6 219978
7 2199978

Below is the Python script in full, followed by a quick example usage.  I’m hoping to do some graphs when I get home.

There’s also a bpaste link here.

"""
Original problem from:
http://www.reddit.com/r/math/comments/sirje/interesting_number_theory_i_think_i_discovered/
"""

def reverse_number(n):
    """Dirty string hack for reversing ints"""
    return int(str(n)[::-1])

def find_fixed_point(func, end_func, initial, show_steps = False):
    """
    Returns the fixed point of a func

   unless end_func(x) is true first- then returns None
    """
    x = initial
    visited = []
    while 1:
        if show_steps:
            print x
        if end_func(x):
            return None
        visited.append(x)
        x = func(x)
        if x in visited:
            return x

def is_cyclic(func, end_func, x, show_steps = False):
    """Returns true if x eventually is visited again by func"""
    return x == find_fixed_point(func, end_func, x, show_steps=show_steps)

def is_cyclic_takkuso(x):
    """True if this is the first number that cycles using takkuso's rules"""
    func = lambda(x): abs(x - reverse_number(x))
    end_func = lambda(x): x < 1
    return is_cyclic(func, end_func, x)

def get_cyclic_takkuso(ndigits):
    """
    Returns all cyclic values using takkuso's rules

    Only tests numbers with ndigits-
    if you want to find 4-digit cyclic numbers,
    this only tests 1,000 through 9,999.

    Note that there may be valid n-digit numbers
    that lead to m-digit cycles,
    where m < n. This function won't find those.
    """
    func = lambda(x): abs(x - reverse_number(x))
    end_func = lambda(x): x < 1

    cycles = set()
    _min = 10**(ndigits-1)
    _max = 10**ndigits

    for x in xrange(_min, _max):
        if is_cyclic(func, end_func, x):
            cycles.add(x)
    return cycles

And some sample usage:

>>> get_cyclic_takkuso(4)
set([2178, 6534])
>>> is_cyclic_takkuso(9900)
False
>>> get_cyclic_takkuso(7)
set([2199978, 6599934])

Getting the 7-digit cycles took quite a long time- anyone have suggestions for speeding calculations up, besides caching values that are known to loop?

Advertisements

Written by delwinna

April 20, 2012 at 6:30 pm

Posted in Puzzles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: