Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса‑Туэ и применяются в алгоритмах фрактального сжатия изображений.
Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее.
По данному n определите количество очень злых чисел, не превосходящих n.
1 Ответ
Можно решить через функции logand и remainder следующим образом:
(defun count-evil-numbers (n)
(let ((evil-count 0))
(dotimes (i n)
(let ((binary-representation (logand i 0x3fffffff)))
(if (or (zerop (remainder binary-representation 2)) (evenp (length binary-representation)))
(incf evil-count)
nil)))
evil-count))