Ключевое слово
21 | 07 | 2018
Новости Библиотеки

Шахматы онлайн

Чессбомб

Welcome, Guest
Username: Password: Remember me

TOPIC: Математика для чайников №3

Математика для чайников №3 08 Июль 2018 13:46 #1171

  • procrastinator
  • procrastinator's Avatar
Это конечно-же изобретение велосипеда, но решил посмотреть случай n=p^l. Тогда phi(n) = p^l-p^(l-1).
f(0,n)=n+l*phi(n)
Если (k,n)=1 (встречается phi(n) раз) f(k,n)=phi(n)
(k,n)=p (phi(n/p) раз) f(k,n)=2*phi(n)
(k,n)=p^2 (phi(n/(p^2)) раз) f(k,n)=3*phi(n)
...
(k,n)=p^(l-1) (phi(p)=p-1 times) f(k)=l*phi(n)
Теперь осталось посмотреть как функция f(k,ab) зависит от f(k,a) и f(k,b), где (a,b)=1 и задача будет решена.

Математика для чайников №3 08 Июль 2018 18:33 #1172

  • Aycon
  • Aycon's Avatar
  • OFFLINE
  • Стрелец
  • Posts: 5
  • Karma: 0
Мда, довольно неочевидное решение. К слову интересует диапазон n не более 10000
Благодарю за уже приложенные усилия)
Last Edit: 08 Июль 2018 18:34 by Aycon.

Математика для чайников №3 08 Июль 2018 18:37 #1173

  • Aycon
  • Aycon's Avatar
  • OFFLINE
  • Стрелец
  • Posts: 5
  • Karma: 0
n не обязательно простое

Математика для чайников №3 08 Июль 2018 20:10 #1174

  • procrastinator
  • procrastinator's Avatar
procrastinator wrote:
Теперь осталось посмотреть как функция f(k,ab) зависит от f(k,a) и f(k,b), где (a,b)=1 и задача будет решена.
Никто не стал этот случай разбирать пока меня не было дома, поэтому продолжу. Доказывать лень, но интуиция мне подсказывает, а простые примеры подтверждают, что f(k,ab)=f(ka,a)*f(kb,b) если (a,b)=1 (взаимно просты), где ka и kb - остатки от деления k на a и b соответственно, т.е. ka=k(mod a) kb=k(mod b).
Поэтому, окончательно решение выглядит так. Разлагаем n на простые множители: n=p1^l1*p2^l2*...pm^lm, считаем остатки числа k: ki=k(mod pi^li).
Тогда f(k,n) = f(k1,p1^l1)*f(k2,p2^l2)*...*f(km,pm^lm), а эти множители мы уже умеем вычислять.

Математика для чайников №3 08 Июль 2018 21:06 #1175

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 32370
  • Thank you received: 69
  • Karma: 24
ув. procrastinator производит впечатление дискретного математика :yess:

Математика для чайников №3 09 Июль 2018 01:24 #1176

  • procrastinator
  • procrastinator's Avatar
Хайдук wrote:
ув. procrastinator производит впечатление дискретного математика :yess:
O yeah, I am discreet, as a Dane ;)

Математика для чайников №3 09 Июль 2018 04:58 #1177

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Стольник
  • Posts: 118
  • Thank you received: 2
  • Karma: 0
procrastinator wrote:
Поэтому, окончательно решение выглядит так. Разлагаем n на простые множители: n=p1^l1*p2^l2*...pm^lm, считаем остатки числа k: ki=k(mod pi^li).
Тогда f(k,n) = f(k1,p1^l1)*f(k2,p2^l2)*...*f(km,pm^lm), а эти множители мы уже умеем вычислять.

Хоть этот Aycon персонаж сомнительный, но назовет ли он это решение решением? Алгоритмом, да. Однако есть алгоритм и много проще, до n = 10 000 по меньшей мере. Берем n квадрат произведений и тупо делим их на n, вычисляя остатки и накапливая статистику. Примерно так: f[i*j % n]++.
Last Edit: 09 Июль 2018 05:15 by сам-пят.

Математика для чайников №3 09 Июль 2018 18:20 #1178

  • Aycon
  • Aycon's Avatar
  • OFFLINE
  • Стрелец
  • Posts: 5
  • Karma: 0
сам-пят wrote:
procrastinator wrote:
Поэтому, окончательно решение выглядит так. Разлагаем n на простые множители: n=p1^l1*p2^l2*...pm^lm, считаем остатки числа k: ki=k(mod pi^li).
Тогда f(k,n) = f(k1,p1^l1)*f(k2,p2^l2)*...*f(km,pm^lm), а эти множители мы уже умеем вычислять.

Хоть этот Aycon персонаж сомнительный, но назовет ли он это решение решением? Алгоритмом, да. Однако есть алгоритм и много проще, до n = 10 000 по меньшей мере. Берем n квадрат произведений и тупо делим их на n, вычисляя остатки и накапливая статистику. Примерно так: f[i*j % n]++.

Алгоритм подошёл бы. Но я ещё не совсем разобрался что тут написал ув. Прокрастинато хд) либо я не обладаю достаточным матаппаратом, либо сбивает с толку специфическое оформление формул.
Last Edit: 09 Июль 2018 18:20 by Aycon.

Математика для чайников №3 09 Июль 2018 18:28 #1179

  • Aycon
  • Aycon's Avatar
  • OFFLINE
  • Стрелец
  • Posts: 5
  • Karma: 0
П.с. и да,графически весьма напоминает видоизменённую функцию Эйлера,но я не был с ней достаточно знаком до этого поста)

Математика для чайников №3 17 Июль 2018 22:10 #1180

  • procrastinator
  • procrastinator's Avatar
Пусть f(k,n)-количество вхождений цифры k в таблицу умножения по модулю n.

Математика для чайников №3 17 Июль 2018 22:34 #1181

  • procrastinator
  • procrastinator's Avatar
Сдаюсь. Текст не очень-то большой, но не имея возможности редактировать пост и не имея предпросмотра, я его замучаюсь набивать. Просто копирование под одним тегом не сработало. Что ж, если не лень, можете удалить все мои пробы пера.

Математика для чайников №3 17 Июль 2018 22:44 #1182

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12595
  • Thank you received: 310
  • Karma: 12
Удалил. Обидно Вас удалять :-) Почему бы Вам не зарегистрироваться наконец и иметь возможность самому удалять и редактировать?! Считаете нам много чести? :-)
Last Edit: 17 Июль 2018 22:45 by Grigoriy.

Математика для чайников №3 17 Июль 2018 23:30 #1183

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 32370
  • Thank you received: 69
  • Karma: 24
предлагаю ув. procrastinator-у поучаствовать в наших полит. перепалках, поскольку производит впечатления весьма культурного человека :beer:

Математика для чайников №3 18 Июль 2018 15:09 #1184

  • procrastinator
  • procrastinator's Avatar
Grigoriy wrote:
Удалил. Обидно Вас удалять :-) Почему бы Вам не зарегистрироваться наконец и иметь возможность самому удалять и редактировать?! Считаете нам много чести? :-)
Отнюдь, скорее наоборот. Я вот на Шпиле зарегистрировался, и где теперь Шпиль? Так что, из любви к этому форуму, я просто обязан стоять в стороне.

Математика для чайников №3 18 Июль 2018 15:49 #1185

  • .Pirron.
  • .Pirron.'s Avatar
  • OFFLINE
  • Посадник
  • Posts: 1371
  • Thank you received: 75
  • Karma: 25
procrastinator wrote:
Grigoriy wrote:
Удалил. Обидно Вас удалять :-) Почему бы Вам не зарегистрироваться наконец и иметь возможность самому удалять и редактировать?! Считаете нам много чести? :-)
Отнюдь, скорее наоборот. Я вот на Шпиле зарегистрировался, и где теперь Шпиль? Так что, из любви к этому форуму, я просто обязан стоять в стороне.
Наоборот, вы просто обязаны провести этот смелый научный эксперимент. Если после вашей регистрации и наш форум лопнет, то это будет, конечно, немалой потерей для нас, но сам по себе этот факт будет даже поинтересней исследований Петровича. Потом можно будет продолжить эксперимент и на других форумах, и в итоге это может привести к настоящей революции в современном научном знании. Не всем это, конечно, понравится, но что такое наши личные интересы по сравнению с интересами Науки?

Математика для чайников №3 18 Июль 2018 19:46 #1186

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 73001
  • Thank you received: 857
  • Karma: 72
procrastinator wrote:
Отнюдь, скорее наоборот. Я вот на Шпиле зарегистрировался, и где теперь Шпиль? Так что, из любви к этому форуму, я просто обязан стоять в стороне.
Дорогой procrastinator, я в общем-то, крайне далек от каких либо рекомендаций по этому поводу

Но Вы же не можете не отметить, что только наш форум в Шахрунете позволяет постить гостям.
В местах, где Вы регистрировались, это было вынуждено. Здесь нет.
Так что это вопрос только лично Вашего удобства
:beer:
Каждому - своё.

Математика для чайников №3 18 Июль 2018 21:12 #1187

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Посадник
  • Posts: 32370
  • Thank you received: 69
  • Karma: 24
ув. procrastinator знал о The Onion, о котором я еле было слыхал :yess:
Moderators: Grigoriy
Рейтинг@Mail.ru