Die binäre quadratische Diagonale

20

Die binäre Quadrat-Diagonale-Sequenz ist wie folgt aufgebaut:

  1. Nehmen Sie die Folge positiver natürlicher Zahlen:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
  2. Wandle jede Zahl in eine Binärzahl um:

    1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, ...

  3. Verketten Sie sie:

    110111001011101111000100110101111001101111011111000010001 ...

  4. Beginnend mit n=1, erzeugen Quadrate mit zunehmender Seitenlänge , ndie von links nach rechts gefüllt ist, von oben nach unten mit den Elementen der obigen Sequenz:

    1
    1 0
    1 1
    100 
    1 0 1
    1 1 0
    1 1 1 1
    0 0 0 1
    0 0 1 1 
    0 1 0 1
    0 1 1 1 1
    0 0 1 1 0
    1 1 1 1 0
    1 1 1 1 1
    0 0 0 0 1
    ...

  5. Nimm die Diagonale (von links oben nach rechts unten) jedes Quadrats:

    1, 11, 100, 1011, 00111, ...

  6. In Dezimalzahl konvertieren (führende Nullen ignorieren):

    1, 3, 4, 11, 7, ...

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die die Sequenz auf eine der folgenden Arten ausgibt:

  • Senden Sie die Sequenz zurück oder drucken Sie sie unbegrenzt aus.
  • Bei Eingabe idie ersten iElemente der Sequenz zurückgeben oder ausdrucken .
  • Bei gegebener Eingabe idas idritte Element der Sequenz zurückgeben oder ausgeben (entweder 0 oder 1 indiziert).

Bitte geben Sie in Ihrer Antwort an, welches Ausgabeformat Sie wählen.

Dies ist , die kürzeste Antwort in jeder Sprache gewinnt.

Testfälle

Hier sind die ersten 50 Elemente der Sequenz:

1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845,17129,55518,134717,151988,998642,1478099,391518,7798320,8530050,21809025,61485963,66846232,54326455,221064493,256373253,547755170,4294967295,1875876391,2618012644,24710258456,6922045286,132952028155,217801183183,476428761596,51990767390,687373028085,1216614609441,7677215985062,15384530216172,22714614479340,15976997237789,0,256145539974868,532024704777005,601357273478135
Laikoni
quelle

Antworten:

10

Schale , 15 bis 14 Bytes

zȯḋm←CtNCİ□ṁḋN

Probieren Sie es online!

Druckt die Ergebnisse fortlaufend als unendliche Liste.

Erläuterung

Ich frage mich, ob es einen besseren Weg gibt, jedes n- te Element aus einer Liste zu holen, als die Liste in n- lange Abschnitte aufzuteilen und den Kopf jedes Abschnitts abzurufen.

      tN          Get a list of all natural numbers except 1. (A)

             N    Get a list of all natural numbers.
           ṁḋ     Convert each to its binary representation and join them 
                  all into a single list.
         İ□       Get a list of squares of all natural numbers.
        C         Cut the list of bits into chunks of corresponding sizes. (B)

zȯ                Zip (A) and (B) together with the following function.
     C            Split the bit list (from B) into chunks of the given length
                  (from A).
   m←             Get the head of each chunk. This is the diagonal of the
                  bit list arranged as a square.
  ḋ               Interpret the resulting bits as binary digits and return
                  the result.

Um es klar zu machen, extrahieren wir die Diagonale eines nxn- Quadrats, indem wir seine lineare Form in Abschnitte der Länge n + 1 aufteilen und das erste Element jedes Abschnitts abrufen :

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]
Martin Ender
quelle
5

Python 2 , 137-85 Bytes

lambda n:int(''.join(bin(x+1)[2:]for x in range(n**3))[n*~-n*(2*n-1)/6:][:n*n:n+1],2)

Probieren Sie es online!

Felipe Nardi Batista
quelle
4

05AB1E , 19 17 16 Bytes

°LbJsLn£θs>ô€нJC

°wird durch 3min den Links ersetzt, da °diese sehr langsam werden.

Probieren Sie es online! oder als Test Suite

Erläuterung

°L                 # push the range [1 ... 10^input]
  bJ               # convert each to binary and join to string
    sLn            # push the range [1 ... input]^2
       £θ          # split the binary string into pieces of these sizes and take the last
         s>ô       # split this string into chunks of size (input+1)
            €н     # get the first digit in each chunk
              JC   # join to string and convert to int
Emigna
quelle
Kannst du nicht ersetzen 3mdurch n?
Erik der Outgolfer
@EriktheOutgolfer: Ja, ich kann, danke! Ich war mir ziemlich sicher, dass das nicht funktioniert hat, aber das lag möglicherweise an Fehlern in einer früheren Lösung. Gleiche Byteanzahl wie °aber viel schneller: P
Emigna
Die Zahlen von 1 bis Eingabe ^ 2 reichen nicht aus . 1, um ^ 3 wie in der Python-Antworten einzugeben, scheint zu genügen.
OVS
@ovs: Ah ja, deshalb habe ich es vorher nicht benutzt. Diesmal habe ich nur die ersten Artikel überprüft. Ich werde auf die vorherige Lösung zurückgreifen (zum Glück bei gleicher
Byteanzahl
3

Schale , 15 Bytes

Dies ist eine etwas andere Herangehensweise an Martins Antwort

moḋz!NCNCṘNNṁḋN

Probieren Sie es online!

Erläuterung:

              N   List of all natural numbers
            ṁḋ    Convert each to it's binary representation and flatten
         ṘNN      Repeat the list of natural numbers according the natural numbers:
                  [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5...]
        C         Cut the list of bits into lists of lengths corresponding to the above
      CN          Cut that list into lists of lengths corresponding to the natural numbers
moḋz!N            For each in the list, get the diagonals and convert from binary.
m                   For each list in the list
   z!N              Zip it with natural numbers, indexing.
 oḋ                 Convert to binary

In Aktion

ṁḋN : [1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1...]

ṘNN : [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8...]

C : [[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1,1],[0,0,0,1]...]

CN : [[[1]],[[1,0],[1,1]],[[1,0,0],[1,0,1],[1,1,0]]...]

m z!N : [[1],[1,1],[1,0,0],[1,0,1,1],[0,0,1,1,1],[0,1,1,1,0,1]...]

oḋ : [1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845...]

H.PWiz
quelle
3

Java (OpenJDK 8) , 215 212 206 202 197 Bytes

i->{String b="",t;int s=0,x=++i,j;for(;--x>0;s+=x*x);while(b.length()<s)b+=i.toString(++x,2);for(j=1,s=0;j<i;System.out.println(i.valueOf(t,2)),s+=j*j++)for(t="",x=s;x<s+j*j;x+=j+1)t+=b.charAt(x);}

Probieren Sie es online!

Roberto Graham
quelle
2

Gelee , 16 Bytes

RBFṁ
R²SÇṫ²C$m‘Ḅ

Probieren Sie es online!

Erläuterung

RBFṁ  Helper link. Input: integer k
R     Range, [1, 2, ..., k]
 B    Convert each to a list of its binary digits
  F   Flatten
   ṁ  Mold to length k

R²SÇṫ²C$m‘Ḅ  Main link. Input: integer n
R            Range, [1, 2, ..., n]
 ²           Square each
  S          Sum
   Ç         Call helper link on the sum of the first n squares
       $     Monadic chain
     ²         Square n
      C        Complement, 1-n^2
    ṫ        Tail, take the last n^2 elements
        m    Modular indexing, take each
         ‘   (n+1)th element
          Ḅ  Convert from list of binary digits to decimal
Meilen
quelle
1

Mathematica, 96 Bytes

Gibt das idritte Element der Sequenz aus (1-indiziert)

Diagonal@Partition[TakeList[Flatten@IntegerDigits[Range[#^3],2],Range@#^2][[#]],#]~FromDigits~2&


Probieren Sie es online!

J42161217
quelle
1

Perl 5 , 92 + 1 ( -p) = 93 Bytes

$s.=sprintf'%b',++$"for 1..$_**3;map{say oct"0b".(substr$s,0,$_*$_,'')=~s/.\K.{$_}//gr}1..$_

Probieren Sie es online!

Xcali
quelle
1

Jelly , 18 Bytes

Völlig anderer Ansatz als Eriks Lösung .

Ḷ²S‘ɓ*3B€Fṫ
Çm‘ḣµḄ

Probieren Sie es online!

Wie es funktioniert

Ḷ²S'ɓ * 3B € Fṫ - Hilfslink (monadisch).

Ḷ - Verringerter Bereich, erzeugt [0, N].
 ² - Vektorisiertes Quadrat (jeweils quadratisch).
  S - Summe.
   "- Inkrement, um die 1-Indexierung von Jelly zu berücksichtigen.
     ɓ - Startet eine separate dyadische Kette.
     * 3 - Der Eingang zur Potenz von 3.
       B € - Konvertieren Sie jeweils in Binär.
         F - Abflachen.
          ṫ - Schwanz. Rückgabe x [y - 1:] (1-indiziert).

Çm'ḣµḄ - Hauptverbindung (monadisch).

Ç - Letzte Verbindung als Monade.
 m '- Modulare Eingabe + 1. Holen Sie sich jedes "Eingabe + 1" -te Element der Liste.
   ḣ - Kopf. Geben Sie das Obige mit Elementen am Index zurück, die höher sind als die beschnittene Eingabe.
    µḄ - Konvertiert von binär in ganzzahlig.

Dank Jonathan Allan 1 Byte gespart !

Mr. Xcoder
quelle
Speichern Sie eine mit einer dyadischen Kette, um Folgendes zu entfernen ³:Ḷ²S‘ɓ*3B€Fṫ
Jonathan Allan
@ JonathanAllan Natürlich, danke! Ich sollte diesen Trick wirklich lernen
Mr. Xcoder
0

Pyth ,  27  20 Bytes

i<%hQ>s.BS^Q3s^R2QQ2

Überprüfen Sie die ersten Testfälle.

Erhält den I. Term der Sequenz, 1 indiziert.

Wie es funktioniert?

i<%hQ>s.BS^Q3s^R2QQ2   - Full program. Q represents the input.

         S^Q3          - Generate the (inclusive) range [1, Q ^ 3].
       .B              - Convert each to binary.
      s                - Join into a single string.
     >                 - Trim all the elements at indexes smaller than:
               ^R2Q      - The elements of the range [0, Q) squared.
              s          - And summed.
  %hQ                  - Get each Q + 1 element of the list above.
 <                     - Trim all the elements at indexes higher than:
                   Q   - The input.
i                   2  - Convert from binary to integer.
Mr. Xcoder
quelle