spamsink: (Default)
[personal profile] spamsink
Например, можно решить одну из задач Джона Конвея, за решение любой из которых обещается премия.

Одну из задач (пятую) недавно решили:

Пусть n - целое положительное число. Запишем его разложение на простые множители обычным образом, например, 60 = 22·3·5, где простые числа записаны в порядке возрастания, а показатель степени 1 не пишется. Опустим показатели степени в строку и удалим знаки умножения, получив число f(n). Повторим.

Таким образом, f(60) = f(22·3·5) = 2235. Далее, т. к. 2235 = 3·5·149, его образ 35149, а т. к. 35149 - простое, его образ - оно само. Следовательно, 60 → 2235 → 35149 → 35149 → ..., мы долезли до простого числа и остановились на нём.

Предполагается, что с любого числа можно долезть до простого, хотя для числа 20 это не было показано. Заметим, что 20 → 225 → 3252 → 223271 → ..., достигая числа из более чем 100 цифр, но всё ещё не простого.

Был найден контрпример:
13532385396179 = 13·532·3853·96179.

Почти по $22.73 за бит.

Date: 2017-06-05 07:06 pm (UTC)
vak: (Default)
From: [personal profile] vak
Будет удивительно, если когда-нибудь эта задача найдет практическое применение. :)

Date: 2017-06-06 09:30 pm (UTC)
stas: (Default)
From: [personal profile] stas
Я думаю, при такой ставке в Макдональдсе будет быстрее :)

Profile

spamsink: (Default)
spamsink

June 2017

S M T W T F S
    1 23
4 5 678910
111213 141516 17
18 1920 21 222324
252627282930 

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 28th, 2017 05:14 am
Powered by Dreamwidth Studios