Ich habe mit ein paar Zahlen rumgespielt und eine Sequenz gefunden, die natürlich auf OEIS läuft. Es ist A005823 : Zahlen, deren ternäre Erweiterung keine Einsen enthält . Es geht:

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

Ich habe ein CJam-Programm geschrieben , das die ersten n dieser Zahlen generiert, indem der Index in binär konvertiert, die Einsen durch Zweien ersetzt und von ternär in dezimal konvertiert wird.

Mir ist auch aufgefallen, dass man jede gerade Zahl erhalten kann, indem man die Summe von zwei Zahlen in der Folge nimmt (manchmal die Zahl mit sich selbst).

Die Herausforderung:

Bei einer nicht negativen geraden Zahl als Eingabe werden die Indizes von zwei Zahlen in der Reihenfolge ausgegeben, in der sich die Summe ergibt. (Beachten Sie, dass manchmal mehrere Paare möglich sind.)

Die Regeln:

• Geben Sie an, ob Sie die 0- oder 1-Indizierung verwenden.
• Wenn Sie als Zeichenfolge ausgeben, setzen Sie ein Trennzeichen zwischen die beiden Indizes.
• Sie dürfen als komplexe Zahl ausgeben.
• Wenn Sie möchten, können Sie jedes gültige Paar ausgeben.
• Code Golf: Die kürzeste Antwort gewinnt

Testfälle

Ich benutze die 0-Indizierung. Hier liste ich jede mögliche Ausgabe für jede Eingabe auf, aber Sie müssen nur eine ausgeben.

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]

Verwandte: Befindet es sich innerhalb des Cantor-Sets?

Schale , 21 14 13 Bytes

-7 Bytes dank der Antwort von @ Neil

-1 Byte, inspiriert von der Parradoc-Antwort von betaveros

Verwendet die 0-Indizierung

mḋTmMo±>ḋ2B3½

Probieren Sie es online!

Erläuterung

            ½    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

Vorherige 21-Byte-Lösung

Zum ersten Mal habe ich eine Verwendung für gesehen ».

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

Probieren Sie es online!

Länger, als ich es mit Tragetaschen zu tun hatte

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>

Erläuterung: Durch Teilen der Eingabe und der Elemente von A005823 durch 2 wird das Problem nicht geändert, die Lösung wird jedoch einfacher, da die ternären Darstellungen jetzt nur 0s und 1s verwenden und daher kein Übertragen zu berücksichtigen ist. Außerdem wird beim Konvertieren vom Element in den Index ein Schritt gespeichert (der Ternär jedes Elements ist doppelt so groß wie der Binärwert seines Index). Beispiele:

                 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

Jelly , 26, 22 , 21 Bytes

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

Probieren Sie es online!

Ein Byte gespart dank @JonathanAllan!

Erläuterung:

                # 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

Python 2 , 51 Bytes

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

Probieren Sie es online!

Die Aufgabe kann folgendermaßen ausgeführt werden:

1. Halbieren Sie die Eingabe
2. In ternäre Liste konvertieren
3. Teilen Sie das in zwei binäre Listen auf, die elementweise dazu addieren
4. Konvertieren Sie diese Listen aus Binärdateien

Wir können die Aufteilung in (3) durchführen, indem wir 0->0,1->1,2->1für die eine Liste und 0->0,1->0,2->1für die andere konvertieren . Das heißt, durch Überprüfung ist der Wert über einem Schwellenwert von 0 oder 1.

Die beiden Werte können durch entsprechende rekursive Funktionen gefunden werden:

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)

Die Funktion fkombiniert diese beiden in einem Listenverständnis. Dies macht es aufgrund der exponentiellen Verzweigung ineffizient.

Wenn komplexe Zahlen ausgegeben werden könnten, könnten wir 10 Bytes einsparen mit:

f=lambda n:n and(n%6>1)+n%6/4*1j+2*f(n/3)

J, ₃₅ 32 Bytes

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

Probieren Sie es online!

0-indiziert und die Eingabe erfolgt monadisch. Gibt alle möglichen Summierungen auf den Wert zurück (behandelt a bund)b a als verschiedene mögliche Summierungen).

Das Konvertieren von einer Booleschen Matrix in Indizes erfordert viel Code ...

Ich möchte auch die Gabel links entfernen, damit ich nicht so viele Klammern und verwenden muss @ -ats verwenden muss, aber ich kann keinen guten Weg finden, dies zu tun (mein alternativer Ansatz speichert keine Bytes ).

Erläuterung

Berücksichtigen Sie zum Erklären und Entgolfen die folgenden Komponenten der Hauptfunktion

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

valid_nums liefert eine boolesche Matrix, in der die Indizes die Indizes der summierten Sequenzwerte sind. Wenn es an diesen Indizes eine Eins gibt, bedeutet dies, dass sich die beiden Zahlen zum Eingabewert summieren.

indizes_of_ones ist ein J-Idiom für die Angabe der Koordinaten derjenigen in einer booleschen Matrix mit willkürlichem Rang

Die Hauptfunktion besteht ganz einfach aus

indices_of_ones@valid_nums

valid_nums

= [: +/~ 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

indizes_of_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 funktioniert in diesem Fall, indem jede Zeile mit der nächsten verbunden wird.

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

Wir können sehen, dass, wenn dies eine Boolesche Matrix wäre, die Koordinaten von Einsen gefunden werden können, indem die Indizes der gerasterten Matrix als Zahlen in der Basis der Form dieser Matrix interpretiert werden, wobei so viele Präpositionalsätze wie möglich verwendet werden, um den armen Leser zu verwirren .

MATL , 22 21 19 17 Bytes

tQ:qBEI_ZA&+=R&fh

Die Ausgabe ist 1-basiert. Das Programm erzeugt alle Lösungspaare. Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Pyth , 37 Bytes

0-indiziert

Auf jeden Fall nicht so gut golfen, wie es sein könnte.

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

Probieren Sie es online!

Pyth , 29 Bytes

Dieser gibt alle möglichen Indexpaare zurück.

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

Probieren Sie es hier aus.

Pyth , 30 Bytes

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

Probieren Sie es hier aus.

Dies gibt die Indexpaare als zurück [LowerIndex, HigherIndex].

Wie funktioniert das?

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. 

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

½3B2>_B™2Bv

Probieren Sie es online!

Algorithmisch ist es sehr ähnlich wie Neils ES6-Antwort . Auf einer niedrigeren Ebene, ebenfalls auffallend ähnlich der Antwort von H.PWiz's Husk . Ich bin amüsiert, dass wir alle drei Überladungen von nutzen durften B.

Nimmt eine Ganzzahl auf den Stapel, hinterlässt eine Liste mit zwei Ganzzahlen auf dem Stapel.

Erläuterung:

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

Python 3 , 122 120 Bytes

-2 Bytes dank Mr. Xcoder!

0-indiziert

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]

Ungolfed:

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]

Probieren Sie es online!

Mathematica, 94 Bytes

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

1-indiziert

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]

Probieren Sie es online!

0-indiziert.
Es gibt das Indexpaar zurück, bei dem ein Index der kleinstmögliche ist (zum Beispiel, wenn 428er zurückgibt 22,31).

Brain-Flak , 220 166 Bytes

-54 Bytes durch Nachschlagen der Modulo-Funktion im Wiki, wodurch einige strukturelle Änderungen möglich sind

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

Probieren Sie es online!

0-indiziert.

Erläuterung

Wie bei vielen anderen Lösungen wird auch hier die ternäre Erweiterung berechnet n/2und in zwei Binärzahlen umgewandelt.

Schritt 1: Teilen Sie die Eingabe durch 2

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

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

Schritt 2: Ternäre Expansion berechnen

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

 ({}(<>))<>         {   (({})){({}[()])<>}{} }{}<> ([{}()]{})         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

Schritt 3: In Lösung konvertieren

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

([]){{}                                                      ([][()])}           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

JavaScript (ES6), 70-72 Byte

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

(0-indiziert und anscheinend fast die gleiche Lösung wie @Neil, auch wenn ich seine Antwort nicht gesehen hatte)

Ich begann mit dem Abrufen des Index von einer Zahl in umgekehrter Reihenfolge: Stringifiziere mit Basis 3, ersetze jede 2durch1 , parse mit Basis 2.

Um zwei Zahlen zu erhalten, und das für jede gerade, müssen wir nur die Hälfte der Eingabe - aber jetzt können auch 1Ziffern auftreten. Also ersetzen wir es vor dem Schritt zum Ersetzen und Parsen durch eine 0in der einen Zahl und eine 2in der anderen Zahl, was die Summe der beiden nicht ändert. Folgendes habe ich mir ausgedacht (die beiden Ersetzungen 1-> 0-or-2 und 2-> 1in einem Schritt):

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

Natürlich unterscheiden sich die beiden Ersetzungskarten (Strings) nur in einem Index, daher sollten wir in der Lage sein, das Array-Literal zu verkürzen, indem wir nur 1und 2mit ersetzen d == 2 ? 1 : x. Oderd-1 || x . Wo-1 funktioniert das gleiche wie bei den beiden unären Operatoren - aber sie sehen erschreckender aus :-)

n/2Ich habe auch versucht, das Array-Literal und die Klammern um mich herum zu vermeiden

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

aber es stellte sich nicht als fruchtbar heraus.

Pyth, 22 Bytes

J.m}1jb3hQxLJhfqsTQ^J2

Probieren Sie es online aus: Demonstration

Erläuterung:

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