Mitad, mitad mitad y mitad

33

Considere la siguiente secuencia de números:

0,12,14,34,18,38,58,78,116,316,516,716,916,1116,1316,1516,132,332,532,

Enumera todas las fracciones binarias en el intervalo unitario .[0,1)

(Para facilitar este desafío, el primer elemento es opcional: puede omitirlo y considerar que la secuencia comienza con 1/2).

Tarea

Escribir un programa (programa completo o una función) que ...

Elija uno de estos comportamientos:

  • Entrada n, salida enésimo elemento de la secuencia (indexado 0 o indexado 1);
  • Entrada n, salida primeros n elementos de la secuencia;
  • No ingrese nada, envíe la secuencia de números infinitos que puede tomar de uno en uno;

Regla

  • Su programa debería admitir al menos los primeros 1000 elementos;
  • Puede elegir generar decimales o fracciones (incorporado, par entero, cadenas) como desee;
    • La entrada / salida como dígitos binarios no está permitida en esta pregunta;
  • Este es el , los códigos más cortos ganan;
  • Lagunas estándar no permitidas.

Casos de prueba

input output
1     1/2     0.5
2     1/4     0.25
3     3/4     0.75
4     1/8     0.125
10    5/16    0.3125
100   73/128  0.5703125
511   511/512 0.998046875
512   1/1024  0.0009765625

Estos ejemplos se basan en una secuencia indexada en 0 con el 0 inicial incluido. Debería ajustar la entrada para adaptar su solución.

Lee mas

  • OEIS A006257
    • Problema de Josefo: . (Anteriormente M2216)a2n=2an1,a2n+1=2an+1
    • 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
  • OEIS A062383
    • : para n > 0 , a n = 2 l o g 2 n + 1 o a n = 2 a na0=1n>0an=2log2n+1.an=2an2
    • 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...
  • A006257 (n) / A062383 (n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumera todas las fracciones binarias en el intervalo unitario [0, 1). - Fredrik Johansson, 14 de agosto de 2006

tsh
fuente
44
"No ingrese nada, envíe la secuencia de números infinitos uno por uno " ¿Tiene que ser uno por uno o también se nos permite generar una lista infinita (posible en Haskell, Elixir, 05AB1E, etc.)?
Kevin Cruijssen
¿Puedo generar una lista de cadenas? eg"1/2" "1/4" "1/8"...
Barranka
@KevinCruijssen La lista infinita está bien siempre que pueda taken elementos de ella más tarde.
tsh
@ Barranka, creo que es aceptable. Eso no es nada diferente para imprimir fracciones en stdout.
tsh
Cuando dice Entrada / Salida como números binarios no permitidos , ¿quiere decir que no podemos escribir una función que devuelva un par si ints, o a doubleen un idioma / implementación donde doubleusa el formato IEEE binary64 ? Espero que no te refieras a tener que analizar una cadena ASCII si queremos tomar una entrada entera. Los tipos enteros normales son binarios en lenguajes como C. ¿O quiere decir que la entrada / salida no puede ser una matriz o cadena de enteros o ceros / unos ASCII?
Peter Cordes

Respuestas:

22

Haskell , 25 bytes

pred.until(<2)(/2).(+0.5)

Pruébalo en línea!

Produce decimales, indexados en uno sin el término cero inicial.

Agrega 0.5 a la entrada, luego reduce a la mitad hasta que los resultados estén por debajo de 2, luego resta 1. Usar una expresión de punto libre ahorra 1 bytes

f n=until(<2)(/2)(n+0.5)-1
xnor
fuente
11

Java 10, 68 64 bytes

¡Primero prueba en code golf!

Opción 1: encontrar el elemento n -ésimo (indexado 1)

-4 bytes gracias a @Kevin Cruijssen

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);}

Este es un método anónimo que encuentra el n -ésimo término quitando el bit más significativo de n , duplicando y añadiendo uno, entonces dividiendo por la siguiente más alta potencia de 2.

Pruébalo en línea!

Tutorial de código:

n->{                      // builds anonymous function with input n
int x=0;                  // stores floor of log(n) (base 2) for most significant digit
for(;n>>++x!=1;);         // calculates floor of log(n) by counting right shifts until 1
return((~(1<<x)&n)        // removes most significant digit of n
*2.+1)                     // multiplies 2 and adds 1 to get the odd numerator
/(1<<x+1);}               // divides by the next highest power of 2 and returns`

Se editará si es necesario imprimir el valor final en lugar de devolverlo.

TCFP
fuente
Bienvenido a PPCG, es bueno tenerte con nosotros :)
Shaggy
Hola, bienvenido a PPCG! Gran primera respuesta, +1 de mi parte. Actualmente es el mismo recuento de bytes que mi respuesta Java, pero aún puede jugar algunas partes de su respuesta para que sea más corta que la mía: {}el bucle posterior puede ser un ;lugar; puedes eliminar el espacio después de return; 2.0puede ser 2.; Y cambiando de n>>x!=1;x++, 1<<xy 1<<x+1para n>>x++!=1;, 1<<x-1, 1<<xrespectivamente, que también ahorra un byte. Pruébelo en línea: 64 bytes . ¡Disfruta tu estancia!
Kevin Cruijssen
Ah, y si aún no lo ha visto: los consejos para jugar golf en Java y los consejos para jugar golf en <todos los idiomas> son muy interesantes de leer. :)
Kevin Cruijssen
Vea mi respuesta de 30 bytes , originalmente basada en la suya, pero golf y golf y golf.
Olivier Grégoire
9

MathGolf , 5 4 bytes

╫\╨]

Pruébalo en línea!

Cómo se vería si el operador funcionara correctamente

╫\)╨]   (")" adds 1 to TOS, making rounding behave as expected)

Pruébalo en línea!

Explicación

╫     Left-rotate all bits in input
 \    Swap top two elements on stack, pushing the input to the top
  ╨   Round up to nearest power of 2
   ]  Wrap in array (just for pretty printing)

Me inspiré en esta pregunta para resolver el problema, creo que mi "propia" solución tenía alrededor de 10-12 bytes.

Tenía la intención de que la ronda hasta la potencia más cercana de 2 devolviera el número en sí mismo si era un número de dos, pero debido a un error se redondea a la siguiente potencia de dos (por ejemplo, 4 -> 8 en lugar de 4 -> 4 ) Esto tendrá que arreglarse más tarde, pero ahora me ahorra un byte.

maxb
fuente
2
No conozco MathGolf, pero si ]no sirve para otro propósito que formatear la salida, diría que no es necesario incluirlo en el recuento de bytes.
Shaggy
2
No estaba seguro de eso. Dado que la pila se imprime en la salida como una cadena unida, genera una pila con los números 1 y 2 como 12. Si todavía cuenta, eliminaré un byte
maxb
Creo que debería dejarlo. A veces guarda un byte para generar la pila como una cadena, a veces le costará un byte.
H.PWiz
@ H.PWiz ese fue mi pensamiento original, ya que parece justo usar las fortalezas de su idioma. Algunos idiomas solo imprimen la parte superior de la pila cuando terminan, algunos lo imprimen como una lista. Por lo general, es una diferencia de 1 byte, pero es parte del desafío.
maxb
8

Java 10, 89 85 70 69 68 bytes

v->{for(float j,t=2;;t*=2)for(j=1;j<t;j+=2)System.out.println(j/t);}

Port of @Emigma's 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to @Arnauld.

Try it online.

Explanation:

v->{                      // Method with empty unused parameter and no return-type
  for(float j,t=2;;       //  Loop `t` from 2 upwards indefinitely,
                   t*=2)  //  doubling `t` after every iteration
    for(j=1;j<t;          //   Inner loop `j` in the range [1, `t`),
                j+=2)     //   in steps of 2 (so only the odd numbers)
      System.out.println( //    Print with trailing new-line:
        j/t);}            //     `j` divided by `t`
Kevin Cruijssen
fuente
1
How often can I say that I half your byte count? Well, I think this is the first time ;-)
Olivier Grégoire
@OlivierGrégoire Dang, now that is an impressive Java answer. :) I saw your 37-byte version as comment on TCFP's answer, but you even stripped off more bytes. It looks so extremely simple now in your 30-byte version, but it's still ingenious how you've golfed it from the initial version. Well done!
Kevin Cruijssen
7

Python 3, 33 bytes

lambda n:(8*n+4)/2**len(bin(n))-1

Try it online!

Outputs decimals, one-indexed without the initial zero term.

xnor
fuente
7

Java (JDK 10), 30 bytes

n->(n+.5)/n.highestOneBit(n)-1

Try it online!

Returns the nth item in the sequence.

This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-)

Intermediate golfs were:

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);} // 64 bytes (TCFP's answer when I started golfing)
n->{int x=0;for(;n>>++x!=1;);x=1<<x;return((~x&n)*2.+1)/x/2;}    // 61 bytes
n->{int x=n.highestOneBit(n);return((~x&n)*2.+1)/x/2;}           // 54 bytes
n->{int x=n.highestOneBit(n);return((~x&n)+.5)/x;}               // 50 bytes
n->((n&~(n=n.highestOneBit(n)))+.5)/n                            // 37 bytes
n->(n-(n=n.highestOneBit(n))+.5)/n                               // 34 bytes
n->(n+.5)/n.highestOneBit(n)-1                                   // 30 bytes, current score
Olivier Grégoire
fuente
And I was sitting here thinking my answer was as short as I could make it, you come along and cut it by more than half! Amazing stuff, definitely deserves a +1 from me.
TCFP
@TCFP It was an iterative process over the span of several hours. I actually posted each intermediate golfing as a comment to your answer, but deleted them as I found better golfs. Thanks for the praise ;-)
Olivier Grégoire
6

05AB1E, 11 8 bytes

Saved 3 bytes thanks to Kevin Cruijssen.

∞oDÅÉs/˜

Try it online!

Explanation

∞         # start an infinite list [1...
 o        # calculate 2**N
  D       # duplicate
   ÅÉ     # get a list of odd numbers up to 2**N
     s/   # divide each by 2**N
       ˜  # flatten
Emigna
fuente
1
-1 byte by using (infinite list starting at 1): ∞oεDÅÉs/}˜
Kevin Cruijssen
@KevinCruijssen: Cool! That's a command I hadn't seen before. Thanks :)
Emigna
1
Ah, and nice way of saving two more bytes due to the implicit mapping.. Hadn't even thought about that, lol..
Kevin Cruijssen
1
:O how is this possible. You condensed the ~2 page question into 8 bytes.
Cullub
I was thinking using the prime numbers and a list of [1,2,4,4,8,8,8,8,16,16,...,2**n] and prepending the correct indexed prime followed by a /... But that wasn't working so well. Well, but not 8-bytes well. Something like 9LoDÅP)ζ.
Magic Octopus Urn
5

PowerShell, 40 bytes

for($i=2;;$i*=2){1..$i|?{$_%2}|%{$_/$i}}

Try it online!

Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.

Starts by setting $i=2, then enters a for loop. Each iteration, we construct a range from 1..$i and pull out the odd values with |?{$_%2}. Those are fed into their own inner loop, where we divide each to get the decimal |%{$_/$i}. Those are left on the pipeline and output when the pipeline is flushed after every for iteration. Each iteration we're simply incrementing $i by $i*=2 to get the next go-round.

AdmBorkBork
fuente
5

Haskell, 35 32 bytes

Edit: -3 bytes thanks to @Delfad0r.

[(y,2^x)|x<-[1..],y<-[1,3..2^x]]

This is an infinite list of integer pairs.

Try it online!

nimi
fuente
5

Haskell, 40 bytes

s=(1,2):[(i*2+u,j*2)|(i,j)<-s,u<-[-1,1]]

Try it online!

Infinite sequence as pairs of integers (starting from (1,2)).

Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway.

This solution is based on the following observation.

Consider the infinite sequence

{12,14,34,18,38,58,78,116,316,}
and apply the following steps.

  • Replace every number ij in the sequence with the list {2i12j,2i+12j}:
    {{14,34},{18,38},{58,78},{116,316},}
  • Join all the lists into a single sequence:
    {14,34,18,38,58,78,116,316,}
  • Add 12 at the beginning of the sequence:
    {12,14,34,18,38,58,78,116,316,}

Notice how you get back to the sequence you started with!

The solution exploits this fact (together with Haskell's laziness) to compute the sequence s.

Delfad0r
fuente
4

Python 2 - 68 66 bytes

-2 bytes thanks to Kevin

from math import*
def g(n):a=2**floor(log(n,2));print(n-a)*2+1,2*a

Try it Online!

Don Thousand
fuente
You can golf 1 byte by changing return 2*(n-a) to return(n-a)*2. And you could save an additional byte by using Python 2 instead of 3, so return can be print (with parenthesis).
Kevin Cruijssen
2
@KevinCruijssen For someone who doesn't use Python, you certainly are a better Python programmer than me.
Don Thousand
Hehe. :D Simple things like this comes with experience I guess. I'm on this site for about two years now I think (EDIT: Since April 2016). I sometimes even suggests things to golf for answers that are written in languages I had never seen before.. Some basic things work in most languages. For example, last week I suggested a golf for a T-SQL answer, and I once suggested a golf in a Red answer. xD
Kevin Cruijssen
2
44 bytes using len and bin instead of log.
ovs
@ovs 42 bytes.
Jonathan Frech
4

Python 3, 53 51 bytes

  • Saved two bytes thanks to mypetlion; reusing default parameters to reset n.
def f(m=2,n=1):n<m and print(n/m)&f(m,2+n)or f(m+m)

Try it online!

Jonathan Frech
fuente
Swap the parameters to save 2 bytes: def f(m=2,n=1):n<m and print(n/m)&f(m,n+2)or f(m+m)
mypetlion
1
@mypetlion Cool, thank you!
Jonathan Frech
4

R, 42 bytes

function(n)c(y<-2^(log2(n)%/%1)*2,2*n-y+1)

Try it online!

Returns a pair Denominator,Numerator. Uses the formula N=2(n2log2(n))+1 from the Josephus sequence and D=2log2(n)+1 from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common!

Giuseppe
fuente
3

Racket, 92 91 bytes

(define(f k(m 2)(n 1))(if(> k 0)(if(=(+ n 1)m)(f(- k 1)(+ m m))(f(- k 1)m(+ n 2)))(/ n m)))

Try it online!

  • Saved a byte thanks to Giuseppe -- removing superfluous whitespace.
Jonathan Frech
fuente
3

MATL, 8 bytes

BnWGEy-Q

Try it online!

Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient.

Explanation, with input 5:

           # implicit input 5
B          # convert to array of bits
           # STACK: [[1 0 1]]
n          # length (place of Most Significant Bit)
           # STACK: [3]
W          # elementwise raise 2^x
           # STACK: [8]
G          # paste input
           # STACK: [8, 5]
E          # double
           # STACK: [8, 10]
y          # copy from below
           # STACK: [8, 10, 8]
-          # subtract
           # STACK: [8, 2]
Q          # increment
           # STACK: [8, 3]
           # implicit end of program, display stack contents
Giuseppe
fuente
2

Shakespeare Programming Language, 426 bytes

,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You be the sum ofyou a cat.Ford:You cat.Scene V:.Ford:Is twice you nicer I?If solet usScene X.You be twice you.Let usScene V.Scene X:.Ford:Remember twice you.You be the sum oftwice the remainder of the quotient betweenI you a cat.Open heart.You big big big big big cat.Speak thy.Recall.Open heart.You be twice the sum ofa cat a big big cat.Speak thy.Let usAct I.

Try it online!

Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline.

JosiahRyanW
fuente
Love it. Lol You be twice the sum of a cat
Cullub
Actually, it's "twice the sum ofa cat a big big cat" (i.e. 10 for some reason).
JosiahRyanW
2

Python 2, 44 bytes

def f(n):m=2**len(bin(n))/4;return 2*n-m+1,m

Try it online!

Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional).

Chas Brown
fuente
1
return 2*n-m+1,m can be print-~n+n-m,m to save 2 bytes.
Kevin Cruijssen
2

Excel 48 28 Bytes

Saved 20 bytes (!) thanks to tsh

=(A1+0.5)/2^INT(LOG(A1,2))-1

=MOD(A1+0.5,2^(INT(LOG(A1,2))))/2^INT(LOG(A1,2))

Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction.

Explanation: Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input.

I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift).

=MOD(A1                        Use MOD for finding what the right digits are
       +0.5                    this will later add the left "1" to the right digits
           ,2^INT(LOG(A1,2)))) Take Log base 2 number of digits on the right
                               this creates the numerator divided by 2 (explained later)
/ 2^INT(LOG(A1,2))             The denominator should be 2^ (Log2 + 1) but instead of 
                               adding a 1 here, we cause the numerator to be divided by 2 instead
                               This gives us a fraction.  In the numerator, we also added .5
                               instead of 1 so that we wouldn't need to divide it in both the
                               numerator and denominator
Then tsh showed how I could take the int/log out of the mod and remove it from numerator/denominator. 

Examples: enter image description here

Keeta
fuente
What about =(A1+0.5)/2^INT(LOG(A1,2))-1?
tsh
2

C++, 97 75 71 bytes

-26 bytes thanks to tsh, ceilingcat, Zacharý

float f(int i){float d=2,n=1;while(--i)n=d-n==1?d*=2,1:n+2;return n/d;}

Testing code :

std::cout << "1\t:\t" << f(1) << '\n';
std::cout << "2\t:\t" << f(2) << '\n';
std::cout << "3\t:\t" << f(3) << '\n';
std::cout << "4\t:\t" << f(4) << '\n';
std::cout << "10\t:\t" << f(10) << '\n';
std::cout << "100\t:\t" << f(100) << '\n';
std::cout << "511\t:\t" << f(511) << '\n';
std::cout << "512\t:\t" << f(512) << '\n';
HatsuPointerKun
fuente
You may just omit if(!i)return 0; since 0 is not required in the challenge.
tsh
1
When trying to golf C-like language. You should avoid using while but try for. for(;exp;) is as same as while(exp) but you can write two more other statement into it. Prefer ?: instead of if else, which would be shorter in most cases.
tsh
1
I don't think you need the (...) around d-n-1.
Zacharý
1

C (gcc), 63 bytes

No input, prints infinite sequence:

f(i,j){for(i=1,j=2;;i+=2,i>j&&(j*=2,i=1))printf("%d/%d ",i,j);}

Try it online!

Annyo
fuente
3
60 bytes.
Jonathan Frech
1
Building on @JonathanFrech 59 bytes
ceilingcat
1

JavaScript (ES6), 44 bytes

Returns the n-th term, 1-indexed.

f=(n,p=q=1)=>n?f(n-1,p<q-2?p+2:!!(q*=2)):p/q

Try it online!

Arnauld
fuente
1

Ruby, 42 bytes

1.step{|i|(1..x=2**i).step(2){|j|p [j,x]}}

Try it online!

Prints integer pairs infinitely, starting from 1/2.

Kirill L.
fuente
1

JavaScript (Node.js), 30 bytes

f=(n,d=.5)=>d>n?n/d:f(n-d,d*2)

Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of 12 which saved several bytes.

Neil
fuente
1

><>, 19 18 bytes

Using xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the ! was superfluous and ; is not required.

2*1+\1-n
2:,2/?(

Try it online!

PidgeyUsedGust
fuente
You should be checking if it is smaller than 2 first, otherwise the first element is -0.25. Fix for the same amount of bytes
Jo King
Thanks! I also managed to remove another byte by reusing the mirrors.
PidgeyUsedGust
Why did you invert the condition? 16 bytes
Jo King
Didn't notice that it would continue the loop. Are we allowed to not properly finish?
PidgeyUsedGust
Yeah, terminating with an error is fine as long as the OP doesn't specify otherwise
Jo King
1

APL (Dyalog Unicode), 15 bytes

1-⍨.5∘+÷2*∘⌊2⍟⊢

Try it online!

Anonymous prefix lambda.

Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.

How:

1-⍨.5∘+÷2*∘⌊2⍟⊢  Anonymous lambda, argument   10
            2⍟⊢  Log (⍟) of  in base 2. 210  3.32192809489...
                 Floor. 3.32192809489...  3
        2*∘       Take that power of 2. 2³  8
       ÷          Use that as denominator
   .5∘+            + 0.5  10.5. Using that as numerator: 10.5÷8  1.3125
1-⍨               Swap the arguments (⍨), then subtract. 1-⍨1.3125  1.3125-1  0.3125
J. Sallé
fuente
1

C# (.NET Core), 69 bytes

a=>{int b=1,c=2;while(a-->1){b+=2;if(b>c){b=1;c*=2;}}return b+"/"+c;}

Try it online!

Ungolfed:

a=> {
    int b = 1, c = 2;   // initialize numerator (b) and denominator (c)
    while (a-- > 1)     // while a decrements to 1
    {
        b += 2;         // add 2 to b
        if (b > c)      // if b is greater than c:
        {
            b = 1;      // reset numerator to 1
            c *= 2;     // double denominator
        }
    }
    return b + "/" + c; // return fraction as string
}
Meerkat
fuente