¡Vete! ¡No-1 está aquí!

16

Estaba jugando con algunos números y encontré una secuencia que, por supuesto, está en OEIS. Es A005823 : Números cuya expansión ternaria no contiene 1's . Va:

a (2n) = 3 * a (n) +2

a (2n + 1) = 3 * a (n + 1)

a (1) = 0

a = 0,2,6,8,18,20,24,26,54 ....

Escribí un programa CJam que genera el primer n de estos números al convertir el índice a binario, reemplazando los 1 con 2 y convirtiendo de ternario a decimal.

También noté que se puede obtener cualquier número par tomando la suma de dos números en la secuencia (a veces el número consigo mismo).

El reto:

Dado cualquier número par no negativo como entrada, genera los índices de dos números en la secuencia que se suman. (Tenga en cuenta que a veces son posibles varios pares).

Las normas:

  • Especifique si está usando indexación 0 o 1.
  • Si sale como una cadena, coloque un delimitador entre los dos índices.
  • Puede salir como un número complejo.
  • Si lo desea, puede generar cada par válido.
  • Code Golf: gana la respuesta más corta

Casos de prueba

Yo uso 0-indexación. Aquí enumero cada salida posible para cada entrada, pero solo necesita emitir una.

0:       [0 0]
 2:       [1 0]
 4:       [1 1]
 6:       [2 0]
 8:       [2 1] [3 0]
 10:      [3 1]
 12:      [2 2]
 14:      [3 2]
 16:      [3 3]
 18:      [4 0]
 30:      [6 2]
 32:      [6 3] [7 2]
 46:      [7 5]
 50:      [7 6]
 120:     [10 10]
 338:     [19 18]
 428:     [30 23] [31 22]
 712:     [33 27] [35 25] [41 19] [43 17] [49 11] [51 9] [57 3] [59 1]
 1016:    [38 37] [39 36]
Gracias a @Luis Mendo por la ayuda en casos de prueba.

Relacionado: ¿Está dentro del conjunto de Cantor?

geokavel
fuente
¿Podemos generar un número complejo de los dos valores? ¿Podemos proporcionar dos funciones, una dando cada valor?
xnor
2
¿Podemos generar todos los valores posibles, o eso va más allá del desafío?
cole
@cole Sí, está bien.
geokavel
Parece que al Sr. Sloane realmente le gustan sus secuencias numéricas. "Hay una secuencia para eso" (TM)
Pharap
1
Como hay varias soluciones para algunas entradas, sería bueno incluir todas las soluciones en los casos de prueba. Este programa muestra todos los pares de soluciones para cada caso de prueba, en el mismo formato que en el texto de desafío (basado en 0, cada par ordenado cada vez más)
Luis Mendo

Respuestas:

10

Casco , 21 14 13 bytes

-7 bytes, gracias a la respuesta JS de @ Neil

-1 byte inspirado en la respuesta Parradoc de betaveros

Utiliza indexación 0

mḋTmMo±>ḋ2B3½

Pruébalo en línea!

Explicación

            ½    Half the input
          B3     Convert to Base 3
   m             Map over the list
    Mo±>ḋ2       Function such that: 0 -> [0,0], 1 -> [0,1], 2 -> [1,1]
        ḋ2       Binary 2, [1,0]
    M            For each in that list
     o±>         check if the argument is greater than it
  T              Transpose
mḋ               Convert each from binary

Solución anterior de 21 bytes

Primera vez que he visto un uso para ».

mḋT»o%2+ȯ?´eḋε%3`-0B3

Pruébalo en línea!

Más tiempo, ya que estaba lidiando con acarreos

H.PWiz
fuente
8

JavaScript (ES6), 75 71 bytes

f=
n=>[1,0].map(i=>parseInt((n/2).toString(3).replace(/./g,c=>+c+i>>1),2))
<input type=number min=0 step=2 oninput=o.textContent=this.value%2?``:f(this.value)><pre id=o>

Explicación: Dividir la entrada y los elementos de A005823 por 2 no altera el problema, sin embargo, simplifica la solución ya que las representaciones ternarias ahora solo usan 0s y 1s y, por lo tanto, no hay que tener en cuenta. También guarda un paso al convertir del elemento a su índice (el ternario de cada elemento es el doble del binario de su índice). Ejemplos:

                 A005823
                  halved
            n in  values A005823
   n n/2  base 3  base 3 indices
   0   0       0   0   0   0   0  
   2   1       1   1   0   1   0
   4   2       2   1   1   1   1
   6   3      10  10   0   2   0
   8   4      11  11   0   3   0
  10   5      12  11   1   3   1
  12   6      20  10  10   2   2
  14   7      21  11  10   3   2
  16   8      22  11  11   3   3
  18   9     100 100   0   4   0
  30  15     120 110  10   6   2
  32  16     121 111  10   7   2
  46  23     212 111 101   7   5
  50  25     221 111 110   7   6
Neil
fuente
6

Gelatina , 26, 22 , 21 bytes

ḶBḤḅ3
ÇŒcS=¥Ðf⁸ḢiЀÇT

Pruébalo en línea!

¡Un byte guardado gracias a @JonathanAllan!

Explicación:

                # Helper link: A005823 to *N* terms
Ḷ               # Lowered range(N)
 B              # Converted to binary
  Ḥ             # Double each digit
   ḅ3           # Converted from base 3 to decimal
                # Main link
Ç               # Last link
 Œc             # All combinations of 2 items (with replacement)
      Ðf        # Remove every combination where this isn't true:
   S=¥          #   The sum of the two items is equal to N
        ⁸Ḣ      # Take the first combination left
          i     # Index of
           Ѐ   # Each element of the combination
             Ç  # In the sequence
              T # Return the truthy indices
DJMcMayhem
fuente
1
@ JonathanAllan Oh, es bueno saberlo Œc. Y sí, Dennis me explicó el problema S=¥.
DJMcMayhem
Parece que necesita agregar el manejo de casos límite para cero por cierto :(
Jonathan Allan
Parece que esto está basado en 1; tal vez valdría la pena que indica que en la respuesta
Luis Mendo
20 bytes
dylnan
3

Python 2 , 51 bytes

f=lambda n:[n and(n/2%3>r)+2*f(n/3)[r]for r in 0,1]

Pruébalo en línea!

La tarea se puede hacer así:

  1. Reducir a la mitad la entrada
  2. Convertir a lista ternaria
  3. Divídalo en dos listas binarias que sumen elementos
  4. Convierte esas listas de binario

Podemos dividir en (3) convirtiendo 0->0,1->1,2->1para una lista y 0->0,1->0,2->1para la otra. Es decir, al verificar, el valor está por encima de un umbral de 0 o 1.

Los dos valores se pueden encontrar mediante las respectivas funciones recursivas:

p=lambda n:n and(n/2%3>0)+2*p(n/3)
q=lambda n:n and(n/2%3>1)+2*q(n/3)

La función fcombina los dos en una lista de comprensión. Esto lo hace ineficiente debido a la ramificación exponencial.

Si se pudieran generar números complejos, podríamos guardar 10 bytes con:

f=lambda n:n and(n%6>1)+n%6/4*1j+2*f(n/3)
xnor
fuente
Supongo que los números complejos están bien.
geokavel
3

J, 35 32 bytes

($#:I.@,)@(=[:+/~3#.+:@#:@i.@>:)

Pruébalo en línea!

0 indexado y la entrada se da de forma monádica Devuelve todas las sumas posibles al valor (trata a by b acomo diferentes sumas posibles).

La conversión de una matriz booleana a índices requiere mucho código ...

También me gustaría eliminar el tenedor de la izquierda para no tener que usar tantos paréntesis y @-ats, pero no puedo encontrar una buena manera de hacerlo (mi enfoque alternativo no guarda ningún byte )

Explicación

Para fines de explicación y desinterés, considere los siguientes componentes de la función principal

valid_nums      =. = [: +/~ 3 #. +:@#:@i.@>:
indices_of_ones =. $ #: I.@,

valid_nums produce una matriz booleana donde los índices son los índices de los valores de secuencia sumados. Si hay uno en esos índices, significa que los dos números suman el valor de entrada.

indices_of_ones es un lenguaje J para dar las coordenadas de los que están en una matriz booleana de rango arbitrario

La función principal se compone simplemente como

indices_of_ones@valid_nums

números_válidos

= [: +/~ 3 #. +:@#:@i.@>:  Input is n
                 #:@i.@>:  Binary numbers in range [0,n]
              +:           Doubled
         3 #.              Interpreted as ternary
     +/~                   Addition table with self (sum all possible pairs)
=                          Equate to n

indices_de_ones

$ #: I.@,
        ,  Ravel matrix into a single list
     I.    Find the indices of ones in that list
  #:       Convert to the base given by
$          The shape of the matrix

,-ravel funciona en este caso uniendo cada fila a la siguiente.

   i.3 3
0 1 2
3 4 5
6 7 8
   , i.3 3
0 1 2 3 4 5 6 7 8

Podemos ver que si se tratara de una matriz booleana, las coordenadas de las mismas se pueden encontrar interpretando los índices de la matriz desordenada como números en la base de la forma de esa matriz utilizando tantas frases preposicionales como sea posible para ayudar a confundir al lector pobre .

col
fuente
1
Sus salidas redundantes están bien.
geokavel
3

MATL , 22 21 19 17 bytes

tQ:qBEI_ZA&+=R&fh

La salida está basada en 1. El programa produce todos los pares de soluciones. Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

t      % Implicit input: n. Duplicate
Q:q    % Range [0 1 ... n]
B      % Convert to binary. Gives a matrix where each row corresponds to a number
E      % Multiply each entry by 2
I_ZA   % Convert each row from ternary to a number
&+     % Matrix of all pair-wise additions
=      % Does each entry equal n?
R      % Upper triangular matrix
&f     % Push row and column indices of nonzero entries
h      % Concatenate horizontally. Implicit didsplay
Luis Mendo
fuente
OP dijo que la producción de todas las soluciones estaba bien en los comentarios
H.PWiz
@ H.PWiz Gracias! No había visto eso
Luis Mendo
2

Pyth , 37 bytes

0 indexado

Ciertamente no ha jugado golf tan bien como podría ser.

KUQJmi:.Bd\1\23KhfqQ+@JeT@JhTsmm,dkKK

Pruébalo en línea!

Agujero de vaca
fuente
1
34 Bytes: hfqQ+@Jmi:.Bd\1\23QeT@JhTsmm,dkUQU. Definitivamente se puede jugar al golf
Mr. Xcoder el
1
33 bytes: hfqQ+@Jmi:.Bd\1\23QeT@JhTsmm,dkUQ
Sr. Xcoder
2

Pyth , 29 bytes

Este devuelve todos los posibles pares de índices.

fqQ+@Kmi:.Bd\1\[email protected]

Pruébalo aquí

Pyth , 30 bytes

hfqQ+@Kmi:.Bd\1\[email protected]

Pruébalo aquí

Esto devuelve los pares de índices como [LowerIndex, HigherIndex].


¿Como funciona esto?

hfqQ+@Kmi:.Bd\1\[email protected]   Full Program. Q means input throughout the whole explanation.

       m          Q               Map over the range [0, Q) with a variable d.
          .Bd                     Convert to binary.
         :   \1\2                 Replace 1 with 2.
        i        3                Convert it from base 3 to integer.
      K                           Assign the mapped range to a variable K.
                         .cUQ2    All possible two-element combinations of the range [0...Q).
    +@             hT@KeT         Sum of the integers on positions in K of the two-element
                                  combination.
 fqQ                              Filter those that equal the input.
h                                 Optional: Head. Take the first element.
                                  Print the result, implicitly. 
Sr. Xcoder
fuente
2

Paradoc (v0.2.10), 11 bytes (CP-1252)

½3B2>_B™2Bv

Pruébalo en línea!

Algorítmicamente es muy parecido a la respuesta ES6 de Neil . En un nivel inferior, también sorprendentemente similar a la respuesta de H.PWiz's Husk . Me divierte que podamos usar las tres sobrecargas de B.

Toma un entero en la pila, deja una lista de dos enteros en la pila.

Explicación:

½           .. Halve input
 3B         .. Convert to ternary
   2        .. 2, which will get implicitly coerced to [0,1]
    >_      .. Greater than, as a block
      B     .. "Bimap": take the block and map it over the Cartesian
            .. product of the last two lists to get a matrix
       ™    .. Transpose
        2Bv .. Convert each row from binary
betaveros
fuente
1

Pitón 3 , 122 120 bytes

-2 bytes gracias al Sr. Xcoder!

0 indexado

def f(a):r=range(a);s=[int(bin(x)[2:].replace(*'12'),3)for x in r];return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Sin golf:

def f(a):
    r=range(a)
    s=[int(bin(x)[2:].replace(*'12'),3)for x in r]
    return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Pruébalo en línea!

Agujero de vaca
fuente
1
Espero que no te importe. Agregué un enlace de TiO.
Sr. Xcoder
1

Mathematica, 94 bytes

(w=#;Position[s,#]&/@#&@@(k=Select)[Tuples[s=k[Range@w,DigitCount[#,3,1]==0&],{2}],Tr@#==w&])& 


1 indexado

J42161217
fuente
1

JavaScript, 120 101 bytes

n=>[(A=[...Array(n+1)].map(Z=(a,b=a)=>b&&3*Z(b/2|0)+b%2*2))[F='findIndex'](a=>z=~A[F](b=>a+b==n)),~z]

Pruébalo en línea!

0 indexado.
Devuelve el par de índices donde un índice es el más pequeño posible (por ejemplo, en el caso de 428que devuelva 22,31).


fuente
1

Cerebro-Flak , 220 166 bytes

-54 bytes buscando la función de módulo en la wiki, permitiendo algunos cambios estructurales

({()<({}[()()])>}{}){({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

Pruébalo en línea!

0 indexado.

Explicación

Al igual que muchas de las otras soluciones, esto calcula la expansión ternaria n/2y la convierte en dos números binarios.

Paso 1: Divida la entrada por 2

({()<({}[()()])>}{})

 {              }     until number becomes zero:
     ({}[()()])       subtract two
( ()<          > {})  push number of iterations

Paso 2: calcular la expansión ternaria

{({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}

 ({}(<>))<>         {   (({})){({}[()])<>}{} }{}<> ([{}()]{})         modulo (from wiki)
           (()()())                                                   use 3 as base
                     ()<                    >                         evaluate as 1 every time the 3 rolls over
                   (                              <          >[()])   push number of rollovers (function is now division with remainder)
{                                                                  }  repeat until quotient is zero, leaving all remainders on stack

Paso 3: Convertir a solución

([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

([]){{}                                                      ([][()])}           repeat while stack height > 1:
                                                                                 (loop happens once when initial stack height is 1, but that's fine)
       <>(({}){})                                                                double smaller output number
                 <>(({}){}                                  )                    double larger output number
                          {                              }{}                     if digit in ternary expansion is nonzero:
                           ()<                          >                        add 1 to larger output number
                              ({}[()]){                }                         if digit is 2:
                                       <>({}())<>(<{}>)                          add 1 to smaller output number
Nitrodon
fuente
0

JavaScript (ES6), 70 72 bytes

n=>[6,4].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x>>d&1),2)) // thanks @Neil
n=>[0,1].map(x=>parseInt((n/2).toString(3).replace(/1|2/g,d=>~-d||x),2))

(Índice 0, y aparentemente casi la misma solución que @Neil, incluso si no hubiera visto su respuesta)

Comencé con recuperar el índice de un número usando el reverso del proceso: stringify con base 3, reemplazar cada 2con 1, analizar con base 2.

Para obtener dos números, y eso para cada par, solo tenemos la mitad de la entrada, pero ahora también 1pueden aparecer dígitos. Por lo tanto, lo reemplazamos con a 0en el número uno y a 2en el otro número, lo que no cambia la suma de los dos, antes del paso de reemplazar y analizar. Esto es lo que se me ocurrió (haciendo los dos reemplazos, 1-> 0-o-2 y 2-> 1en un solo paso):

n=>["001","011"].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x[d]),2))

Por supuesto, los dos mapas de reemplazo (cadenas) difieren solo en un índice, por lo que deberíamos poder acortar el literal de la matriz solo reemplazando 1y 2con d == 2 ? 1 : x. O d-1 || x. ¿Dónde -1hace lo mismo que los dos operadores unarios, pero parecen más aterradores :-)

Tratando de evitar la matriz literal y el paréntesis alrededor n/2, también se me ocurrió

n=>Array.from(parseInt,(h=n/2,i)=>parseInt(h.toString(3).replace(/1|2/g,d=>~-d||i),2))

pero no resultó fructífero.

Bergi
fuente
También comencé con la ["001","011"]versión (bueno, mis nombres de variables eran diferentes)
Neil
Creo que .replace(/./g,d=>d>>1|x)ahorra 2 bytes.
Neil
@Neil Desafortunadamente, eso no funciona d="0"y x=1- el dígito debería quedarse0
Bergi
Sí, lo resolví después de probar algunos casos de prueba más. (Y desde entonces se me ocurrió otra variante, pero eso está en mi respuesta, me temo.)
Neil
1
Oh, muy bien, y pensé que estaba siendo inteligente para vencer a tu versión anterior ...
Neil
0

Pyth, 22 bytes

J.m}1jb3hQxLJhfqsTQ^J2

Pruébelo en línea: demostración

Explicación:

J.m}1jb3hQxLJhfqsTQ^J2
        hQ                input + 1 
 .m                       find all values of [0, 1, 2, ..., input], where
     jb3                     value converted to base 3
   }1                        check if it contains the digit 1
                          this boolean ^ is false
J                         store this list in variable J

                   ^J2    every pair of J
              f           filter for pairs with
                sT           sum of pair
               q             equal
                  Q          the input
             h            take the first of these pairs
          xLJ             and find the corresponding indices of J
Jakube
fuente