Попробую. Из графика частотности видно, что решающее значение для общего показателя компрессии имеют лишь несколько первых интервалов: 6, 12 и 2, 4, 8, 10. По сути без разницы, какие коды использовать — лишь бы эти несколько были наиболее короткими. В предложенном варианте они наиболее короткие.
Наверно я чего-то не понял. Это уменьшит таблицу НАТУРАЛЬНЫХ чисел, исключив из них 3/4 и все неподозрительные на простоту. Таблицу ПРОСТЫХ это увеличит, добавив в нее помимо простых еще и подозрительные на простоту.
Построение на лету хорошо для разовых задач, но усложнение программирования ставит под вопрос выполнимость самих таких задач. Прикладные задачи потребуют дополнить построение на лету кэшированием и сложность программирования возрастет в разы.
Гм, хорошая идея :) В голову не пришло.
Отдельные вещи можно проверить у альтернативных источников. Например, последнее простое в использованной мной таблице 999999999989, имеет порядковый номер 37607912018, здесь primes.utm.edu/nthprime этому можно получить подтверждение. Значит, во всяком случае пропусков нет. А вот проверить на предмет перестановок и подмен — тут увы. Только поэлементное сравнение с такой же таблицей, либо поштучная проверка на простоту. Собственно, этим-то простые и замечательны, что другого способа нет.
Берем все числа в промежутке, который вызывает у Вас подозрения. И проверяем все по очереди :)
Вообще-то таблицы так и строят — берут все числа по очереди. Как тут пропустить что-то можно?
У меня такое чувство. что половина из отметившихся в комментариях не уловила, суть идеи в строго детерминированном характере частотности интервалов. Традиционное же кодирование исходит из некоторых общих представлений о данных. Поскольку частотность интервалов детерминирована, нет никаких проблем рассчитать эффективность любого другого метода кодирования, на последней диаграмме я несколько таких примеров привел. Есть предложение? Посчитайте сами. Итоги в студию.
Не думаю, что будет большая разница между традиционной компрессией последовательности простых и последовательности интервалов между простыми, между ними нет принципиальной разницы. Т.е., сжатие будет приличное, но не олимпийское. Пробовать, честно говоря, лень :)
Точно. За одним минусом — с этого момента восстановление простого по его порядковому номеру становится нетривиальной задачей, что уравнивает метод с более продвинутым.
Построение на лету хорошо для разовых задач, но усложнение программирования ставит под вопрос выполнимость самих таких задач. Прикладные задачи потребуют дополнить построение на лету кэшированием и сложность программирования возрастет в разы.
Отдельные вещи можно проверить у альтернативных источников. Например, последнее простое в использованной мной таблице 999999999989, имеет порядковый номер 37607912018, здесь primes.utm.edu/nthprime этому можно получить подтверждение. Значит, во всяком случае пропусков нет. А вот проверить на предмет перестановок и подмен — тут увы. Только поэлементное сравнение с такой же таблицей, либо поштучная проверка на простоту. Собственно, этим-то простые и замечательны, что другого способа нет.
Вообще-то таблицы так и строят — берут все числа по очереди. Как тут пропустить что-то можно?
У меня такое чувство. что половина из отметившихся в комментариях не уловила, суть идеи в строго детерминированном характере частотности интервалов. Традиционное же кодирование исходит из некоторых общих представлений о данных. Поскольку частотность интервалов детерминирована, нет никаких проблем рассчитать эффективность любого другого метода кодирования, на последней диаграмме я несколько таких примеров привел. Есть предложение? Посчитайте сами. Итоги в студию.