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, 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 6

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 7

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 8

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 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

x86 32-bit machine code, 16 bytes

0F BC C1 0F B3 C1 E3 01 40 0F AB C1 91 14 00 C3

Try it online!

Uses the fastcall calling convention – argument in ECX, result in EAX.

This function leaves values with only one 1 bit (powers of 2) unchanged; other values are modified by moving the lowest 1 bit one place up, or to the bottom if the position above it is already 1. Thus, a non-power-of-2 is in a cycle of length equal to the position of its second-lowest 1 bit.

In assembly:

.global f
f:
    bsf eax, ecx    # Set EAX to the position of the lowest 1 bit in ECX.
    btr ecx, eax    # Remove that 1 bit from ECX.
    jecxz s         # Jump if ECX is 0 (had only one 1 bit).
    inc eax         # (Otherwise) Increase EAX by 1.
s:  bts ecx, eax    # Set to 1 the bit in ECX at position EAX,
                    #  and set the carry flag (CF) to its former value.
    xchg ecx, eax   # Exchange registers, moving the number into EAX.
    adc al, 0       # Add 0+CF to the low byte of EAX.
    ret             # Return.

Answer 11

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 12

JavaScript (ES6), 43 bytes

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

Answer 13

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 14

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.

Answer 15

05AB1E, 4 bytes

WĀiÁ

Port of @orlp's Pyth answer, so make sure to upvote him/her as well.

Try it online or verify some test cases.

Explanation:

W     # Push the smallest digit of the (implicit) input-integer (without popping)
 Āi   # If this is NOT 0:
   Á  #  Rotate the integer once towards the right
      # (after which the resulting integer is output implicitly)

Answer 16

x86 32-bit machine code, 11 bytes

0F BD C8 D1 E8 73 FC 0F AB C8 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in EAX.

This function takes a number's binary digits (without leading zeroes) and rotates them right until the highest one is again a 1.

In assembly:

f:  bsr ecx, eax    # Set ECX to the highest position of a 1 bit in EAX.
r:  shr eax, 1      # Shift EAX right by 1 bit, with the lowest bit going into CF.
    jnc r           # Repeat if CF=0.
    bts eax, ecx    # Set to 1 the bit in EAX at position ECX.
    ret             # Return.