24
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ "there must be a cycle of length 1, of length 2, and so on" Should this be interpreted as "there must be at least a cycle of length 1, at least one of length 2, and so on" or "there must be exactly a cycle of length 1, one of length 2, and so on". \$\endgroup\$
    – Bakuriu
    Jul 24, 2015 at 11:25
  • \$\begingroup\$ @Bakuriu At least one cycle of each positive length. \$\endgroup\$
    – isaacg
    Jul 24, 2015 at 20:03

16 Answers 16

14
\$\begingroup\$

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
\$\endgroup\$
0
9
\$\begingroup\$

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]
\$\endgroup\$
3
  • \$\begingroup\$ Damn, this is the pattern I also was going for, but with a closed form. \$\endgroup\$
    – orlp
    Jul 23, 2015 at 16:01
  • 1
    \$\begingroup\$ Interesting.. the a-values follow the sequence A000124. But I guess you already knew that :P \$\endgroup\$
    – Kade
    Jul 23, 2015 at 16:04
  • \$\begingroup\$ Note that this sequence is oeis.org/A066182. \$\endgroup\$
    – orlp
    Jul 23, 2015 at 16:06
8
\$\begingroup\$

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:

M(n) = floor((1 + sqrt(1 + 8*(n - 1))) / 2) B(n) = M(n)*(M(n) - 1) / 2 f(n) = B(n) + ((n - B(n) + 1) mod M(n))

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Déjà vu! Cool to see it in two languages! \$\endgroup\$ Jul 23, 2015 at 23:48
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 43 bytes

f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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.
\$\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.