(Снова про сокращение дробей)
PS. Забавная задачка для олимпиадного раздела образовалась.
Стало интересно во всех ли системах счисления имеются такие примеры "неправильного" сокращения дробей, думать лень, добавил ещё один цикл в программу, запустил. Оказалось для систем счисления по основаниям 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и т.д. до 997 нетривиальных (не в форме xx/xx) примеров двухзначных дробей не имеется. Ряд подозрительно совпадает с множеством простых чисел ... И похоже этот факт доказывается совсем несложно.
Количество разных нетривиальных дробей для разных систем счисления:
ну и т.д.
О, ну как обычно, стоило лишь посчитать самому, как по результату легко нашлось и в OEIS:
A259981.
Интересно, для большинства чисел количество дробей чётно. Исключения - квадраты чётных чисел.
Наименьшее количество дробей при основаниях
- и снова, за исключением начала, очень похоже на
A077068.