?

Log in

No account? Create an account

Фракталы

«Если долго всматриваться в бездну — бездна начнёт всматриваться в тебя» © Ницше

Previous Entry Share Next Entry
Немного хаоса в этот блог 2
xcontcom


На днях задумался о длине периода десятичной записи дроби 1/n. Наделал графиков и получил еще немного хаоса...


Чтобы не запутаться в формулировках, опишу проблему простыми словами.
Из школьного курса математики (5-й класс), мы знаем, что число (1/n) можно записать в виде десятичной дроби. В школе нас научили делить в столбик и рассказали, что бывают конечные десятичные дроби и бесконечные (периодические) десятичные дроби. Например:
1/4=0.25 - конечная десятичная дробь
1/7=0.(142857)142857142... - периодическая дробь. В ней повторяются цифры 142857. Эти цифры - "период" дроби. Длина периода, для дроби 1/7 равна 6.
Больше нам в школе о десятичных дробях ничего не рассказывали. А между тем, тема интересная.

У меня, при взгляде на такую запись числа, возникают два вопроса:
1. Для каких n получим периодическую дробь, а для каких - конечную.
2. Как от n зависит длина периода.


Ответ на первый вопрос очевиден. Периодическую дробь получим, если в разложении знаменателя (n) на простые делители имеются числа, которых нет в разложении основания (b) системы счисления, в которой мы эту дробь записываем.
Пример. Основание нашей привычной десятичной системы (b=10) можно разложить на простые делители 2 и 5. Если в разложении знаменателя дроби (n) присутствуют только эти цифры (2 и 5) - получаем конечную дробь:
1/20=1/(2*2*5)=0.05
1/16=1/(2*2*2*2)=0.0625
Другими словами, конечную дробь получаем для любых чисел n=(2^m)*(5^k), где m и k целые числа.

Если же туда в знаменатель вкрадется тройка или любое другое простое число - получим периодическую дробь:
1/14=1/(2*7)=0.0(714285)
1/12=1/(2*2*3)=0.08(3)
1/21=1/(3*7)=0.(047619)

Это правило работает для любых систем счисления. На картинке (кликабельно) записал первые 24 дроби для первых 9 систем счисления:

Без названия (4).png

Десятичная система счисления - атавизм, поэтому дальше ее не рассматриваю. Пользуемся мы этой системой только из-за того, что у нас 10 пальцев на руках. Наши предки считали на пальцах. Когда пальцев стало не хватать - придумали записывать единичку в следующий разряд (10). Больше эта система счисления ни к чему не привязана. 10 - это, ни просто число, ни квадрат целого числа, и даже ни число Фибоначчи. 10 - скучно число. Я бы даже сказал "мутное".
Вот 2 - отличное число. В двоичной системе счисления конечные дроби получаем только для n=2^m (m-целое число). К тому же в периоде дроби присутствуют только два знака - 1 и 0, что гораздо удобнее для поиска закономерностей.

Ответ на второй вопрос (как от n зависит длина периода дроби) менее очевиден и до сих пор до конца не изучен. Выявили только несколько закономерностей, которые общую картину не проясняют. Над этой проблемой в свое время ломал голову известный математик Гаусс (Википедия называет его одним из величайших математиков всех времён, «королём математиков»).
Вот тут http://kvant.mccme.ru/pdf/2000/02/kv0200semenova.pdf пишут:

Великий немецкий математик Карл Фридрих Гаусс, будучи гимназистом, обращал дроби вида 1/p, где p - простое число, отличное от 2 и 5, в бесконечные десятичные дроби: в каждом случае он с поразительным терпением ожидал, когда знаки начнут повторяться. Ему хотелось понять, как зависит длина периода такой дроби от p.
Выписывание полного периода, скажем, для p=47 - утомительное занятие (46 знаков!). Однако Гаусс не терял надежды и продолжал вычисления: он выписывал периоды для всех простых чисел p<1000. Главная закономерность, которую он обнаружил, состоит в том, что длина L(p) наименьшего периода такой дроби является делителем числа p - 1, иногда совпадая с ним.


Вот дядька заморочился - все периоды выписывать. Это надо сидеть и 1 делить "в столбик" на 47, пока знаки не начнут повторяться. А, между тем, закономерность он так до ума и не довел (это "иногда" - очень туманное).
Я вот задумался, а если бы у Гаусса или, скажем, у Эйлера, был бы компьютер - каких бы они бед в математике могли бы начудить.

Мы с вами не Гауссы и не Эйлеры, но компьютер у нас есть. А компьютер - отличное средство для визуализации данных. Ну и визуально эти данные намного проще воспринимать и намного проще искать в них закономерность.

Записал первые 52 двоичные дроби. Красными линиями отметил период в каждой из них:



Длина периода хаотична.

Также можем записать в матрицу все дроби от 1/1 до 1/100 с точностью до сотого знака:
1/1=1.1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1/2=0.1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1/3=0.0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1/4=0.0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1/5=0.0011001100110011001100110011001100110011001100110011001100110011001100110011001100110011001100110011
1/6=0.0010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
1/7=0.0010010010010010010010010010010010010010010010010010010010010010010010010010010010010010010010010010
1/8=0.0010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
...
1/100=0.0000001010001111010111000010100011110101110000101000111101011100001010001111010111000010100011110101

И дальше получившуюся матрицу преобразовать в картинку, закрасив единички белым цветом, а нолики - черным:



Ух, какая красота получается. Не видать закономерности!

Матрица 1000х1000:



Опять же хаос, но тут уже можно увидеть необычные вертикальные линии. Первая такая линия - где-то в районе 360-го знака (после запятой, в двоичной дроби) чаще встречаются нолики. Горизонтальные линии - это степени двойки.

Мне кажется или картиночка фрактальная?

Матрица 3000х3000 (кликабельно):



Матрица 500х12000:






Recent Posts from This Journal

  • Как сварить пиво в домашних условиях.

    Две недели занимался дикой фигней - варил пиво. Но пиво не простое, а... под кат Технология варки пива довольно незамысловатая. 1. Проращивается…

  • ((x*y) mod m) mod n

    Очень любопытные картинки получаются! Берем x, умножаем на y (соответствующие координаты пикселя на картинке). Получили число. Взяли остаток…

  • И еще немного о двоичной системе

    Немного с алиасингом поиграемся. Без предисловия. Под кат. В предыдущей записи разобрались с делением. А как у нас обстоят дела с умножением?…


  • 1
Как всё сложно. Я гуманитарий однако.

А мне понравилось. Представить в матрице, чтобы взглянуть на убедительный хаос - весьма оригинально. Надеюсь, правильно поняла "задумку".)
П.С. Любопытны диагональные линии из левого верхнего угла, как лучи из одной точки, а точка за пределами матрицы.

Edited at 2017-10-12 11:42 am (UTC)

Точка четко в левом верхнем углу.

Тогда, наверное, есть какая-то закономерность в этом хаосе все-таки. "Лучи" исходят из одной точки. "Угол наклона", интересно, от чего зависит...

Плоскость один я вижу?

Даже не представляю что это, но похоже на код на акцизных марках, PDF-417 вроде

ни черта не понял но на всякий случай накатил

не исповедимы пути извилин, когда по ним бегают тараканы...) наверное так и рождаются теории... вероятности, относительности и иного хаоса бегущих)

А теперь считаем эту матрицу QR-ридером, и видим там зашифрованную цифру «42». )))

А так можно было?)

Это любопытно, но имеет ли практический смысл. Скажем так, если можно графически представлять различные математические последовательности, то почему бы не представить в графическом виде поток вычисляемый в коде биткоина. Таким образом, понимая, что у человека неплохой графический процессор можно изобрести графический или ручной, человеческий майнинг. Идея моя, мозги ваши.

А вот если например зафигачить такие матрицы в разных системах исчисления (не только 2, но и 3, 4 и т.д), а значения выделять разными цветами... Все время кажется, что что-то осмысленное получится.

Уж не знаю, почему для Вас 10 -- число неинтересное, а два -- интересное, но вообще высчитать период дроби можно с использованием арифметики остатков.

Например, какой период у дроби 1/7 в двоичной системе? 2-1 на 7, естественно, не делится, 2^2-1 -- тоже, а вот 2^3-1 уже годится. Получается, что период должен быть трёхзначным. И если бы Вы подчеркнули самые первые три цифры после запятой, то увидели бы, что он представляет собой частное (2^3-1)/7.

В обычной же десятичной системе наименьшее число вида 10^n-1, которое делится на 7, можно посчитать так. 9 делится на 7 с остатком 2, 99=10х9+9 -- с тем же остатком, что 2х3+2, то есть 1. Далее, аналогично, 1х3+2 -- остаток 5, 5х3+2 -- остаток 3, 3х3+2 -- остаток 4, 4х3+2 -- остатка нет. Значит, наименьшее подходящее число равно 10^6-1, и период шестизначный.

Разумеется, если знаменатель дроби сам представляет собою степень двойки, дробь в двоичной системе получится конечной, а если делится на 2, но при этом имеет и другие простые делители -- то с предпериодом.

Попробуйте применить к картинкам ренорм-преобразование с небольшим модулем....

классический битовый поток

По фракталам я философски заморочен. Подписываюсь

осталось придумать систему исчисления, в которой были бы только простые числа и любое число на любое делилось бы без остатка :)

вчера читала эти посты, рассматривала картинки. Поняла, что делаю все не так. Убрала глупости со стола. Расставила странные предметы. Заложила за ухо карандаш. Растрепала волосы. И дальше смотрела картинки с тревогой на лице, периодически нервно возвращаясь к предыдущим, рисовала в блокноте хаотичные схемы. Стучала себя по лбу ладонью "ну конечно! это же очевидно" Спасибо! Почувствовала себя фанатичным программистом профессором на несколько минут. А так бы и не довелось.

  • 1