Удивительное совпадение

[kthxbye]

Обратите внимание на разность последовательностей 1+A000120(A025480(n)) и A106487(n): c 0 по 63 члены они совпадают, далее до 101 разность по модулю - единица.

Можно как-нибудь получить больше членов A106487?

-- 06.06.2021, 21:34 --

А, там даже комментарий есть внизу покруче, но он мало что добавляет относительно продолжения.

[svv]

На страничке OEIS A106487 есть программа на Lisp-подобном языке Scheme. С этим языком я не то что не знаком, даже и названия не слышал.
Я зашёл на сайт JDoodle (https://www.jdoodle.com), там есть онлайн-компилятор Scheme и небольшая демонстрационная программка, показывающая, что компилятор работает. Вместо неё вставил программу из OEIS. Столкнулся с двумя вопросами:
1) Как выводить результаты? Вот так:
(display (A106487 12))
вычисляет и выводит A106487(12). Примитивно, но Вы наверняка найдёте что-то более удобное.
2) Программа в исходном виде выдаёт ошибку:
*** ERROR: unbound variable: |1+|
Я не знаю, что значит «неограниченная переменная», но понял, что надо сделать. В двух местах программы встречается сомнительная конструкция (1+ i), я заменил её на (+ 1 i).

В итоге программа вместе с тестовыми запросами (вычислить A106487 для $n=0...10$) приобрела такой вид:

Используется синтаксис Scheme

(define (A106487 n) (cond ((zero? n) 1) (else (apply + (map A106487 (map shr (on-bit-indices n)))))))
(define (shr n) (if (odd? n) (/ (- n 1) 2) (/ n 2)))
(define (on-bit-indices n) (let loop ((n n) (i 0) (c (list))) (cond ((zero? n) (reverse! c)) ((odd? n) (loop (/ (- n 1) 2) (+ 1 i) (cons i c))) (else (loop (/ n 2) (+ 1 i) c)))))
(display (A106487 0)) (newline)
(display (A106487 1)) (newline)
(display (A106487 2)) (newline)
(display (A106487 3)) (newline)
(display (A106487 4)) (newline)
(display (A106487 5)) (newline)
(display (A106487 6)) (newline)
(display (A106487 7)) (newline)
(display (A106487 8)) (newline)
(display (A106487 9)) (newline)
(display (A106487 10)) (newline)
 

Все ответы правильные. Мне кажется, это ещё более удивительное совпадение.
Пожалуйста, прежде всего, проверьте, что для всех $n$ до 101 программа выдаёт правильные результаты.

[Sender]

svv в сообщении #1521486 писал(а):

*** ERROR: unbound variable: |1+|
Я не знаю, что значит «неограниченная переменная»

Мне кажется, тут это скорее означает "несвязанная".

[svv]

Точно, unbound же, а не unbounded.

[Geen]

svv в сообщении #1521486 писал(а):

Я не знаю, что значит «неограниченная переменная», но понял, что надо сделать. В двух местах программы встречается сомнительная конструкция (1+ i), я заменил её на (+ 1 i).

"не замкнутая" (в смысле исчисления высказываний). "i" может быть просто переменной, а может быть мнимой единицей. Что бы выделить второй случай часто пишут "1i" (лучше без пробела - более читабельно).
Но вот, возможно заменить нужно было на "1+1i" (иначе не понятно зачем плюс).

[svv]

(n-1)/2 в Scheme записывается как
(/ (- n 1) 2)
И, аналогично, 1+i записывается как (+ 1 i)
Жуть.

[Geen]

svv в сообщении #1521490 писал(а):

Жуть

не знал.....
но польская нотация это удобно только если скобки необязательны

[Ivan_B]

svv в сообщении #1521490 писал(а):

Жуть.

В Lisp есть возможность выполнять часть кода(макросы) на этапе компиляции. Макросы используются для модификации кода.
Простой синтаксис превращает макросы в очень мощный и гибкий инструмент.
Имея в распоряжении только goto можно в пару строк расширить язык, добавив if, while, for.
(На самом деле в Lisp, кроме стандартного набора, есть язык макрос loop для написания циклов)
Сравните это с теми преградами, которые нужно преодолеть, чтобы добавить range-based for в С++.

[svv]

Ivan_B, понятно.

В той программе, что я привёл, для вывода значений $\operatorname{A106487}(n)$ при $n=0...10$ я просто $11$ раз подряд вызываю функцию с конкретным значением $n$, потому что не знаю, как записать цикл. Вы не могли бы подсказать, как это сделать? Обратите внимание, что слово loop в программе встречается, т.е. компилятор Scheme на JDoodle его понимает.

[kthxbye]

svv в сообщении #1521486 писал(а):

Пожалуйста, прежде всего, проверьте, что для всех $n$ до 101 программа выдаёт правильные результаты.

Сделал слепляющую формулу в Excel для команды вывода, все верно. Прогнал пока 4096 значений, результат следующий:

0 64
1 128
2 64
0 64
1 128
2 64
0 64
1 128
2 64
0 64
1 128
2 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
1 64
2 128
3 64
2 64
3 128
4 64
2 64
3 128
4 64
2 64
3 128
4 64
2 64
3 128
4 64

Справа паттерн угадывается, но еще не факт.

[svv]

Слева $4$ раза повторяется $0,1,2$, потом $8$ раз повторяется $1,2,3$. Интересно, сколько раз повторится $2,3,4$?

[Ivan_B]

svv в сообщении #1521563 писал(а):

не знаю, как записать цикл. Вы не могли бы подсказать, как это сделать?

Используется синтаксис Scheme

(define (print-A106487 n) 
   (display (A106487 n))
   (newline))

(dotimes (i 11) (print-A106487 i))

То, что я писал о loop относится к Сommon Lisp.

[svv]

Спасибо.