Welcome, guest | Sign In | My Account | Store | Cart

Why?

  • Thinking about a sequence of odd numbers where numbers divisible by 3 are not part of it I came to a sequence starting with 5, 7, 11, 13, 17, 19, ...
  • The interesting property of this sequence is that the sequence of differences between the individual elements are 2,4,2,4,2,...

How?

  • I'm not a math expert (unfortunately) but I could imagine that there is a quite simple formula to get this.
  • However I thought that using different combinations of defined functions a script could do the favour for me.

Result?

  • Formula: (((-1)**(x-1))+1)+2 -> Simplified -> -1**(x-1) + 3 (now clear to you?)
  • You have to look for the sequence [4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2]

Out of scope:

  • Does not check for using lambda functions only and "x" only in the lambda functions.
  • The Python script does not simplify functions like changing ((x+1)+1) to x+2 - would be an interesting recipe - by the way :)

Please note

  • You should not add other functions than lambda.
  • You should always use "x" in your formular.
  • Be aware that the actual setup runs a few minutes (about 3 minutes) and you can imagine - surely - that adding further functions will definitely increase the runtime.

Side effects?

  • Quite funny to produce a sequence of nines with (((-1)**(2*x))+2)**2.
  • If you apply the first binomial theorem (a+b)^2 = a^2 + 2ab + b^2 then you see why!

What I have learned from this?

  • The biggest nightmare I did have with the Sequence class because of not knowing how to generate unique elements of this in a set (__eq__ and __hash__ are required); and I have to ensure that the hash code is calculated once only.
  • The 'combineFunctions' was interesting to me. I have never used 'inspect.getsource' before.
  • A few minutes does not sound much but for developing all times with more than 30 seconds are not comfortable. There are just 325 sequences and to investigate for certain sequences you probably have to have some more formula. Maybe I would have to take another approach for that.
Python, 104 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
"""
    @author  Thomas Lehmann
    @file    sequenceBuilder.py
    @brief   generates sequences throughout different combinations of functions
"""
import sys
import itertools
import inspect
import re

class Sequence(object):
    """ represents a sequence and the used formula """
    def __init__(self, sequence, formula):
        """ storing one sequence and the relating formula """
        self.sequence = sequence
        self.formula  = formula
        self.hashCode = hash(tuple(self.sequence))

    def __eq__(self, other):
        """ required for unique elements in set container """
        return self.hashCode == other.hashCode

    def __lt__(self, other):
        """ required for sorting only """
        for a,b in zip(self.sequence, other.sequence):
            if a < b: return True
            if a > b: return False
        return False

    def __hash__(self):
        """ required for unique elements in set container """
        return self.hashCode

    def __repr__(self):
        return "%s - %s" % (self.sequence, self.formula)

class SequenceBuilder(object):
    def __init__(self):
        """ initializes for empty containers only """
        self.registeredFunctions = []
        self.sequences = set()

    def add(self, function):
        """ adds a function to the list of functions
            @param function is expected to be a lambda expression
        """
        self.registeredFunctions.append(function)

    def createSequences(self, fromPosition, toPosition):
        """ using the permutation of all functions to generate sequences
            @param fromPosition start position/index/value
            @param toPosition end position/index/value
        """
        self.sequences = set()
        for r in range(1,len(self.registeredFunctions)):
            for functions in itertools.permutations(self.registeredFunctions, r):
                position = fromPosition
                sequence = []
                while position <= toPosition:
                    value = position
                    for function in functions:
                        value = function(value)
                    sequence.append(value)
                    position += 1
                self.sequences.add(Sequence(sequence[0:], self.combineFunctions(functions)))

    def combineFunctions(self, functions):
        """ generates a combined formula as used for the calculation
            @param functions the list of individual functions (lambda code)
            @return the combined formula
            @note out of scope is the simplification (like: (x+1)+1 => x+2)
        """
        expression = ""
        for function in reversed(functions):
            match = re.match(".*\((?P<expression>lambda.*)\).*", inspect.getsource(function))
            if match:
                functionCode = match.group("expression")
                functionCode = functionCode[functionCode.find(":")+1:].strip()
                if not len(expression):
                    expression = functionCode
                else:
                    expression = expression.replace("x", "("+functionCode+")")
        return expression

def main():
    """ application entry point """
    print("Sequence builder v0.1")
    print("...Using Python %s" % sys.version.replace("\n", " - "))
    builder = SequenceBuilder()
    builder.add(lambda x: x-1)
    builder.add(lambda x: x-2)
    builder.add(lambda x: x+1)
    builder.add(lambda x: x+2)
    builder.add(lambda x: 2*x)
    builder.add(lambda x: x**2)
    builder.add(lambda x: (-1)**x)
    # takes a while...
    builder.createSequences(1, 20)
    print("...%d sequences found:" % len(builder.sequences))
    for sequence in sorted(builder.sequences):
        print(sequence)

if __name__ == "__main__":
    main()

In one comment you see the extract of the full output!

1 comment

Thomas Lehmann (author) 9 years, 9 months ago  # | flag
[code]
C:\Tools\pypy-1.7\pypy.exe M:/Python/prototyping/prototyping.py
Sequence builder v0.1
...Using Python 2.7.1 (930f0bc4125a, Nov 27 2011, 11:58:57) - [PyPy 1.7.0 with MSC v.1500 32 bit]
...320 sequences found:
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] - ((-1)**(2*x))+1
[2, 2, 10, 26, 50, 82, 122, 170, 226, 290, 362, 442, 530, 626, 730, 842, 962, 1090, 1226, 1370] - ((((2*x)-1)-2)**2)+1
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21] - x+1
[2, 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, 123, 146, 171, 198, 227, 258, 291, 326, 363] - ((x-1)**2)+2
[2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4] - (((-1)**x)+1)+2
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40] - 2*x
[2, 4, 10, 20, 34, 52, 74, 100, 130, 164, 202, 244, 290, 340, 394, 452, 514, 580, 650, 724] - 2*(((x-1)**2)+1)
[2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 325, 362, 401] - (x**2)+1
[2, 6, 2, 6, 2, 6, 2, 6, 2, 6, 2, 6, 2, 6, 2, 6, 2, 6, 2, 6] - 2*(((-1)**x)+2)
[2, 6, 18, 38, 66, 102, 146, 198, 258, 326, 402, 486, 578, 678, 786, 902, 1026, 1158, 1298, 1446] - ((2*(x-1))**2)+2
[2, 7, 14, 23, 34, 47, 62, 79, 98, 119, 142, 167, 194, 223, 254, 287, 322, 359, 398, 439] - ((x+1)**2)-2
[2, 8, 18, 32, 50, 72, 98, 128, 162, 200, 242, 288, 338, 392, 450, 512, 578, 648, 722, 800] - 2*(x**2)
[2, 10, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10] - ((((-1)**x)+2)**2)+1
[2, 10, 26, 50, 82, 122, 170, 226, 290, 362, 442, 530, 626, 730, 842, 962, 1090, 1226, 1370, 1522] - (((2*x)-1)**2)+1
[5, 11, 21, 35, 53, 75, 101, 131, 165, 203, 245, 291, 341, 395, 453, 515, 581, 651, 725, 803] - (2*((x**2)+2))-1
[5, 15, 29, 47, 69, 95, 125, 159, 197, 239, 285, 335, 389, 447, 509, 575, 645, 719, 797, 879] - ((2*((x+1)**2))-1)-2
[5, 17, 37, 65, 101, 145, 197, 257, 325, 401, 485, 577, 677, 785, 901, 1025, 1157, 1297, 1445, 1601] - ((2*x)**2)+1
[7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45] - (2*(x+2))+1
[7, 13, 23, 37, 55, 77, 103, 133, 167, 205, 247, 293, 343, 397, 455, 517, 583, 653, 727, 805] - (2*((x**2)+2))+1
[7, 14, 23, 34, 47, 62, 79, 98, 119, 142, 167, 194, 223, 254, 287, 322, 359, 398, 439, 482] - ((x+2)**2)-2
[/code]