6
\$\begingroup\$

Your task is to build a piece of code that generates an aperiodic sequence of integers, either by outputting one every time it iterates, or by taking an integer n and returning the nth number in that sequence.

Now, the sequence 1, 2, 3, 4, 5, 6, ... is itself aperiodic, so I'm going to introduce a few limitations to the definition of "aperiodic" used in this problem to weed out the trivial cases:

  • The sequence must not be periodic modulo any integer m > 1. So a sequence like the powers of 2 would repeat 2, 4, 8, 6 all the time modulo 10, and therefore not count. (It would also repeat 0 modulo 2.)

  • The sequence must not become periodic after a certain number of operations - e.g. 1 2 4 8 6 2 4 8 6 ... is still considered periodic even though 1 never appears again.

  • The generation code must only use integers. So a piece of code that calculated the nth digit of pi (without calculating it in some integer form first) would not be acceptable.

Now, obviously every sequence performed with limited computer memory will eventually either be periodic or run out of memory, but if you can prove that your function, given infinite memory and time, will never loop back to a previous state, then it is acceptable.

The shortest code that does the above wins.

\$\endgroup\$
13
  • \$\begingroup\$ What about strings? Can we use strings or arrays of numbers? \$\endgroup\$ – John Dvorak Sep 10 '13 at 4:04
  • 8
    \$\begingroup\$ Btw you can calculate the nth digit of pi using only integers. \$\endgroup\$ – Howard Sep 10 '13 at 5:39
  • 1
    \$\begingroup\$ I doubt anyone can beat my 2-character golfscript solution. Anyone fluent in APL? \$\endgroup\$ – John Dvorak Sep 10 '13 at 6:34
  • 2
    \$\begingroup\$ @JanDvorak Burlesque - 2 bytes: gl. Does the same thing as your GolfScript solution. \$\endgroup\$ – primo Sep 10 '13 at 7:25
  • 1
    \$\begingroup\$ You might be interested in my work on BiEntropy, which evaluates the order and disorder of a finite binary sequence. The sequence 1,2,3,4,5,6... is in fact periodic (ie the first differences 0,0,0,0,0....of the sequence are perfectly periodic). arxiv.org/abs/1305.0954 The paper includes an evaluation of the disorder of the prime number sequence and the digits of pi and e etc. \$\endgroup\$ – Grenville Croll Sep 21 '13 at 21:10
18
\$\begingroup\$

Golfscript, 2 characters

`,

(stringify (`) the number and count (,) the digits)

J, 3 characters

#q:

is the count (#) of the prime factors (q:) of its input.

The vector form involves more bookkeeping, but that's not our contestant:

#@q:L:0&.<

the first 40 terms are: 0 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 1 3 1 3 2 2 1 4 2 2 3 3 1 3 1 5 2 2 2 4 1 2 2 4

see more at OEIS

The sequence is 1 at every prime position, 2 at every prime multiple of a prime, 3 at every prime multiple of a product of two primes...


If you are not convinced this is aperiodic, here are plenty of other sequences:

##:

(the number of bits = floor of the base-2 logarithm)

+/#:

(count of 1-bits in the binary representation of the number). This (reduced under any modulus)

#b#:
+/b#:

(the same in base-b)

<.^.
>.^.
<.b^.
>.b^.

(floor or ceiling of the (natural) log - this time without stringification)

*./#:
+./b#:
*./b#:

(GCD or LCM of all base-b digits (except GCD of bits won't work))

1{#:!
9{#:!
({#:@!)

(second/tenth/nth highest bit of the factorial of n)

(=<.&.%:)

(Is the number equal its floor under the square root operation? Is the number equal the square of the floor of its square root? Is the number a square?)

\$\endgroup\$
7
  • \$\begingroup\$ I don't think anybody here needs convincing that the pattern of primes is aperiodic. \$\endgroup\$ – breadbox Sep 10 '13 at 6:30
  • \$\begingroup\$ @breadbox the pattern of primes is aperiodic, but what about the pattern of numbers that have an odd number of prime power divisors? \$\endgroup\$ – John Dvorak Sep 10 '13 at 6:30
  • \$\begingroup\$ For the J part of the solution, why not just use p: (the nth prime)? After all, you said yourself that the pattern of primes is aperiodic. \$\endgroup\$ – Volatility Sep 10 '13 at 7:21
  • \$\begingroup\$ @Volatility the sequence of primes is periodic modulo 2 as all primes are odd. If rules 1+2 are not meant to be taken together, then a simple factorial will do (as noted by Peter Taylor). -:<:p: would likely be a valid sequence, but it's a bit longer. \$\endgroup\$ – John Dvorak Sep 10 '13 at 7:25
  • 2
    \$\begingroup\$ If rules 1 and 2 aren't taken together then the primes do work, because the first one is even. Even if they are, the prime indicator function works, although that seems to be 4 characters in J: 1 p:. \$\endgroup\$ – Peter Taylor Sep 10 '13 at 8:27
4
\$\begingroup\$

Python, 48 25 bytes

Volatility's version, using string operations:

f=lambda a:int(`2**a`[0])

Numerical version (48 bytes):

def f(a):
 m=2**a
 while m>9:
  m/=10
 return m

Sequence it returns (first 100 terms):

1 2 4 8 1 3 6 1 2 5 1 2 4 8 1 3 6 1 2 5 1 2 4 8 1 3 6 1 2 5 1 2 4 8 1 3 6 1 2 5
1 2 4 8 1 3 7 1 2 5 1 2 4 9 1 3 7 1 2 5 1 2 4 9 1 3 7 1 2 5 1 2 4 9 1 3 7 1 3 6
1 2 4 9 1 3 7 1 3 6 1 2 4 9 1 3 7 1 3 6

This returns the first digit of the ath power of 2, which is aperiodic because log10 2 is irrational, and no multiple of it besides 0 will be an integer. (So while it may look periodic for a long time, eventually there will always be something to break the period.)

I could probably golf for whitespace, but I'm not experienced with that.

\$\endgroup\$
4
  • \$\begingroup\$ Why not just f=lambda a:int(`2**a`[0])? \$\endgroup\$ – Volatility Sep 10 '13 at 4:53
  • \$\begingroup\$ @Volatility Good question. I didn't think of using string operations. \$\endgroup\$ – Joe Z. Sep 10 '13 at 4:54
  • \$\begingroup\$ Why do people assign their lambdas to variables? \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 19:34
  • \$\begingroup\$ @CatsAreFluffy Unnamed lambdas weren't always allowed. \$\endgroup\$ – user45941 Mar 10 '16 at 7:52
4
\$\begingroup\$

Python, 14

int.bit_length

This generates the following sequence:

>>> f=int.bit_length
>>> [f(i) for i in range(20)]
[0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ lambda x:`x`[0] \$\endgroup\$ – CalculatorFeline Mar 9 '16 at 20:54
3
\$\begingroup\$

Perl -p, 7 characters

$_.=/1/

Takes an integer n on the standard input and outputs the nth number in the following sequence:

11 2 3 4 5 6 7 8 9 101 111 121 131 141 151 161 171 181 191 20 211 22 23 24 25 26...
\$\endgroup\$
2
\$\begingroup\$

Sage, 7

Sage has the integer-part-of-the-square-root function built-in :

f=isqrt

[f(n) for n in [0..20]]
->  [0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]

A number of OEIS sequences are also Sage built-ins named using the OEIS index, and would score a length of 16; e.g.,

f=sloane.A000120

f;[f(n) for n in [0..20]
->  1's-counting sequence: number of 1's in binary expansion of n.
    [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2]
\$\endgroup\$
1
\$\begingroup\$

Perl, 19 18 characters

Simplicity itself:

sub f{"@_"=~/(.)/}

Given an integer n, the function f returns the nth number in the sequence.

For those not conversant in Perl, f returns the leading decimal digit in n. As the sequence continues, you get progressively longer runs of the current number. Thus the sequence is transparently aperiodic, and avoids devolving into any of the trivial cases listed above.

\$\endgroup\$
1
  • \$\begingroup\$ +1 for simplicity. $_[0] may be replaced with "@_" for one byte. \$\endgroup\$ – primo Sep 10 '13 at 7:13
0
\$\begingroup\$

RETURN, 9 bytes (noncompetitive)

0[' ,1+$¦{\3}§.1!]!

Try it here.

Make sure to run using "timed run," because this is an infinite stream. Also replace \3 with character U+0003.

Explanation

Basically just outputs each number reversed. I couldn't find any periodicity, but please tell me if you do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.