20

Двоично-квадрат-диагональная последовательность строится следующим образом :

Возьмем последовательность положительных натуральных чисел:
```
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
```

Преобразовать каждое число в двоичное:

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

Объединить их:

11011100101110111100010011010101111001101111011111000010001 ...

Начиная с n=1, генерируйте квадраты с увеличивающейся длиной стороны, 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
```
```
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
```
```
...
```
Возьмите диагональ (сверху слева внизу справа) каждого квадрата:
```
1, 11, 100, 1011, 00111, ...
```
Преобразовать в десятичную (игнорируя ведущие нули):
```
1, 3, 4, 11, 7, ...
```

задача

Напишите программу или функцию, которая выводит последовательность одним из следующих способов:

Вернуть или распечатать последовательность бесконечно.
При заданном вводе iвернуть или распечатать первые iэлементы последовательности.
При заданном вводе iвернуть или распечатать iэлемент последовательности (либо 0, либо 1 проиндексированный).

Пожалуйста, укажите в своем ответе, какой выходной формат вы выберете.

Это код-гольф , выигрывает самый короткий ответ на каждом языке.

Контрольные примеры

Вот первые 50 элементов последовательности:

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

code-golf sequence binary base-conversion binary-matrix Laikoni
источник

10

Шелуха , 15 14 байт

zȯḋm←CtNCİ□ṁḋN

Попробуйте онлайн!

Постоянно печатает результаты в виде бесконечного списка.

объяснение

Интересно, есть ли лучший способ получить каждый n- й элемент из списка, чем разбивать список на куски длины n и извлекать заголовок каждого куска.

      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.

Чтобы было ясно, мы извлекаем диагональ квадрата nxn , разбивая его линейную форму на куски длиной n + 1 и извлекая первый элемент каждого кусочка:

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]

Мартин Эндер
источник

5

Python 2 , 137 85 байт

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)

Попробуйте онлайн!

Фелипе Нарди Батиста
источник

4

Python 3 , 96 94 байта

lambda i:int(''.join(bin(x+1)[2:]for x in range(i**3))[sum(x*x for x in range(i))::i+1][:i],2)

Попробуйте онлайн!

овс
источник

4

05AB1E , 19 17 16 байтов

°LbJsLn£θs>ô€нJC

°заменяется 3mв ссылках, как °правило, очень медленно.

Попробуйте онлайн! или как тестовый набор

объяснение

°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
источник

Вы не можете заменить 3mна n?

Эрик Outgolfer

@EriktheOutgolfer: Да, я могу, спасибо! Я был почти уверен, что это не сработало, но это могло быть связано с перегибами в более раннем решении. Тот же счетчик байтов, что и °гораздо быстрее: P

Emigna

Числа от 1 до ввода ^ 2 недостаточны . 1 для ввода ^ 3, как в питоне ответов, кажется, достаточно.

овс

@ovs: Ах да, именно поэтому я не использовал его ранее. На этот раз я проверил только первые пару пунктов. Я вернусь к предыдущему решению (к счастью, с тем же количеством байтов)

Emigna

3

Шелуха , 15 байт

Это принимает несколько иной подход к ответу Мартина

moḋz!NCNCṘNNṁḋN

Попробуйте онлайн!

Объяснение:

              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

В бою

ṁḋ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
источник

3

Java (OpenJDK 8) , 215 212 206 202 197 байт

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

Попробуйте онлайн!

Роберто Грэм
источник

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

( 197 байтов )

Кевин Круйссен

2

Python 2 , 91 байт

i=n=1;s=''
while 1:
 s+=bin(i)[2:];i+=1
 if s[n*n:]:print int(s[:n*n:n+1],2);s=s[n*n:];n+=1

Попробуйте онлайн!

печатает последовательность бесконечно

овс
источник

2

Желе , 16 байт

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

Попробуйте онлайн!

объяснение

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

миль
источник

1

Mathematica, 96 байт

Выходы на iго элемента последовательности (1-индексированных)

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

Попробуйте онлайн!

J42161217
источник

1

Perl 5 , 92 + 1 ( `-p`) = 93 байта

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

Попробуйте онлайн!

Xcali
источник

1

Желе , 18 байт

Совершенно другой подход по сравнению с решением Эрика .

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

Попробуйте онлайн!

Как это устроено

S²S'ɓ * 3B € Fṫ - вспомогательная ссылка (монадическая).

Ḷ - пониженный диапазон, генерирует [0, N).
 ² - векторизованный квадрат (квадрат каждый).
  S - сумма
   '- Инкремент, чтобы учесть 1-индексацию желе.
     ɓ - запускает отдельную двоичную цепочку.
     * 3 - вход в степень 3.
       B € - конвертировать каждый в двоичный файл.
         F - Свести.
          T - Хвост. Вернуть x [y - 1:] (1-индексированный).

Çm'ḣµḄ - главная ссылка (монадическая).

Last - Последняя ссылка как монада.
 m '- модульный ввод + 1. Получить каждый «вход + 1» -й элемент списка.
   Head - руководитель. Вернуть вышеупомянутое с элементами с индексом выше, чем урезанный ввод.
    µḄ - конвертировать из двоичного в целое число.

Сохранено 1 байт благодаря Джонатану Аллану !

Мистер Xcoder
источник

Сохраните один, используя диадическую цепочку, чтобы удалить ³:Ḷ²S‘ɓ*3B€Fṫ

Джонатан Аллан

@JonathanAllan Конечно, спасибо! Я должен действительно изучить этот трюк

мистер Xcoder

0

Желе , 22 байта

²Rµ²Ṭ€Ẏ0;œṗBẎ$³ịs³ŒDḢḄ

Попробуйте онлайн!

Эрик Outgolfer
источник

0

Pyth , 27 20 байтов

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

Проверьте первые несколько тестовых случаев.

Получает I- й член последовательности, 1 проиндексирован.

Как это устроено?

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.

Мистер Xcoder
источник

Диагональная последовательность двоичных квадратов

задача

Контрольные примеры

Ответы:

Шелуха , 15 14 байт

объяснение

Python 2 , 137 85 байт

Python 3 , 96 94 байта

05AB1E , 19 17 16 байтов

Шелуха , 15 байт

Объяснение:

В бою

Java (OpenJDK 8) , 215 212 206 202 197 байт

Python 2 , 91 байт

Желе , 16 байт

объяснение

Mathematica, 96 байт

Perl 5 , 92 + 1 ( `-p`) = 93 байта

Желе , 18 байт

Как это устроено

Желе , 22 байта

Pyth , 27 20 байтов

Как это устроено?

Диагональная последовательность двоичных квадратов

задача

Контрольные примеры

Ответы:

Шелуха , 15 14 байт

объяснение

Python 2 , 137 85 байт

Python 3 , 96 94 байта

05AB1E , 19 17 16 байтов

Шелуха , 15 байт

Объяснение:

В бою

Java (OpenJDK 8) , 215 212 206 202 197 байт

Python 2 , 91 байт

Желе , 16 байт

объяснение

Mathematica, 96 байт

Perl 5 , 92 + 1 ( -p) = 93 байта

Желе , 18 байт

Как это устроено

Желе , 22 байта

Pyth , 27 20 байтов

Как это устроено?

Perl 5 , 92 + 1 ( `-p`) = 93 байта