Every Possible Cycle Length

Question

A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, take the following function:

Input:  n    1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9

If we start with n=1, f(n)=5, f(f(n))=f(5)=4, f(f(f(n)))=f(4)=3, f(f(f(f(n))))=f(3)=1.

This is written (1 5 4 3). Since there are 4 unique numbers in this loop, this is a cycle of length 4.

---

Your challenge is to write a program or function which has cycles of every possible length. That is, there must be a cycle of length 1, of length 2, and so on.

In addition, your function/program must be from the positive integers to positive integers, and it must be bijective, meaning that there must be a exactly one input value for every possible output value, over all positive integers. To put it another way, the function/program must compute a permutaion of the positive integers.

---

Details: Any standard input/output system is allowed, including STDIN, STDOUT, function argument, return, etc. Standard loopholes prohibited.

You do not need to worry about the limitations of your data types - the above properties need only hold under the assumption that an int or float can hold any value, for instance.

There are no restrictions on the behavior of the function on inputs which are not positive integers, and those inputs/outputs will be ignored.

---

Scoring is code golf in bytes, shortest code wins.

Answer 1

Pyth, 11 8 bytes

.<W-0zz1

A lot more boring than my previous answer.

Every number that contains a 0 digit maps to itself. Any other number maps to the number that has its digits rotated by 1. So for example:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123

Answer 2

Python 2, 56 55 54 bytes

n=input()
a=b=1
while a+b<=n:a+=b;b+=1
print(n+~a)%b+a

Here's the first 21 outputs:

[1, 3, 2, 6, 4, 5, 10, 7, 8, 9, 15, 11, 12, 13, 14, 21, 16, 17, 18, 19, 20]

The pattern is obvious if we break the list up into chunks like so:

 1    2  3    4  5  6    7  8  9  10    11  12  13  14  15    16  17  18  19  20  21
[1]  [3, 2]  [6, 4, 5]  [10, 7, 8, 9]  [15, 11, 12, 13, 14]  [21, 16, 17, 18, 19, 20]

Answer 3

Pyth, 25 bytes

+hK/*J/h@h*8tQ2 2tJ2%-QKJ

This is the same sequence as @Sp3000, but with a closed form. The closed form is:

Answer 4

Python3, 40 bytes

n=input();print([n[1:]+n[0],n]['0'in n])

Every number that contains a 0 digit maps to itself. Any other number maps to the number that has its digits rotated by 1. So for example:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123

Answer 5

Ruby, 22+1=23

With command-line flag -p, run

~/(.)(.?)/
$_=$1+$'+$2

When given as input a string representation of a number (with no trailing newline), it keeps the first digit constant, then rotates the remainder left, so 1234 becomes 1342.

This can be reduced to 21 characters with $_=$1+$'+$2if/(.)(.)/, but prints a warning.

Answer 6

Ruby, 16+1=17

With command-line flag -p, run

$_=$_[/.0*$/]+$`

This is a more complicated function than my other answer, but happens to be more golfable (and tolerant to trailing newlines). It takes the last nonzero digit of the input, plus any trailing zeroes, and moves it to the beginning of the number. So 9010300 becomes 3009010. Any number with n nonzero digits will be part of an n-length cycle.

Input is a string in any base via STDIN, output is a string in that base.

Answer 7

Python, 43

The inverse of Sp3000's function, implemented recursively.

f=lambda n,k=1:n>k and k+f(n-k,k+1)or n%k+1

The function is a one-cycle followed by a two-cycle followed by a three-cycle, ...

(1)(2 3)(4 5 6)(7 8 9 10)(11 12 13 14 15)...

The operation n%k+1 acts as a k-cycle on the numbers 1..k. To find the appropriate k to use, shift everything down by k=1, then k=2, and so on, until n<=k.

Answer 8

Pyth, 15 bytes

The shortest answer so far that uses numeric operations rather than string operations.

.|.&Q_=.&_=x/Q2

    Q                input
            /Q2      input div 2
           x   Q     that XOR input
          =          assign that to Q
         _           negate that
       .&       Q    that AND Q
      =              assign that to Q
     _               negate that
  .&                 input AND that
.|               Q   that OR Q

The effect of this function on the binary representation is to extend the rightmost block of 1s into the next 0; or if there is no 0, to reset it back to a single 1:

10010110100000 ↦  
10010110110000 ↦  
10010110111000 ↦  
10010110111100 ↦  
10010110111110 ↦  
10010110111111 ↦
10010110100000  

Pyth, 26 bytes, fun variant

.|.&Q_h.&/Q2+Qy=.&/Q2_h.|y

    Q                           input
         /Q2                    input div 2
             Q                  input
                  /Q2           input div 2
                         yQ     twice input
                       .|  Q    that OR input
                     _h         NOT that
                .&              (input div 2) AND that
               =                assign that to Q
              y                 twice that
            +                   input plus that
       .&                       (input div 2) AND that
     _h                         NOT that
  .&                            input AND that
.|                          Q   that OR Q

Performs the above operation simultaneously to all blocks of 1s, not just the rightmost one—still using only bitwise and arithmetic operations.

1000010001001 ↦
1100011001101 ↦
1110011101001 ↦
1111010001101 ↦
1000011001001 ↦
1100011101101 ↦
1110010001001 ↦
1111011001101 ↦
1000011101001 ↦
1100010001101 ↦
1110011001001 ↦
1111011101101 ↦
1000010001001

Answer 9

Brachylog, 5 bytes

∋0&|↺

Try it online!

Port of @orlp's Pyth answer. Comes out simple and neat:

∋0    % If input contains a 0 (since input is a single number, "contains" ∋ treats it as an array 
      %   of its digits, so this means "if any of input's digits are 0")
&     % Then output is the input
|     % Otherwise
↺     % Circularly shift the input once, and unify that with the output

I originally wanted to port @Sp3000's Python solution, but that took a whopping 23 bytes:

⟧∋B-₁⟦++₁A≤?;A--₁;B%;A+

Try it online!

Answer 10

Swift 1.2, 66 bytes

func a(b:Int){var c=0,t=1,n=b
while n>c{n-=c;t+=c++}
print(n%c+t)}

Input:  1,   2, 3,  4, 5, 6,   7, 8, 9, 10,   11, 12, 13, 14, 15
Output: 1,   3, 2,  5, 6, 4,   8, 9, 10, 7,   12, 13, 14, 15, 11

Answer 11

JavaScript (ES6), 43 bytes

f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i

Answer 12

Matlab(189)

  function u=f(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if ~isempty(z),t=y(y~=max(y));if isempty(t),u=y(end)*2^(nnz(y)-1);else,g=max(t);e=primes(g*2);u=n/g*e(find(e==g)+1);end,end,end

---

• The function:

  Maps any integer according to its prime factors, if the number is nil or factorised into 2 or 1, the number is mapped to itself, otherwise we pick the biggest prime factor of this number, then we increment the remaining different prime factors by the closest bigger prime factor until we reach the number biggest_prime^n where n is the sum of all exponents of all factors, once we reach that amount, we turn to max_prime*2^(n-1) and we reproduce the same cycle again.

Answer 13

Matlab(137)

  function u=h(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if~isempty(z),e=nnz(y);f=nnz(z);if(~mod(e,f)&e-f)u=n/2^(e-f);else,u=u*2;end

---

• A slightly similar approach, multiplying gradually any number not equal to {0,1,2^n} by 2 until we stumble upon an exponent of 2 which is divisible by sum of exponents of other prime factors. then we move to the beginning of the cycle dividing by 2^(sum of exponents of other primes). the other numbes are mapped to themselves.