Остатки...сладки?

[Ktina]

Депастрап Ксения Игоревна задумала четырёхзначное число и написала остатки от деления этого числа на 2, на 3, …, на 101 (всего 100 остатков). Могло ли так оказаться, чтобы среди выписанных чисел было не меньше 20 восьмёрок? А не меньше 24 восьмёрок?

[hippie]

Ответ: могло.

Если исходное число 5048, то 26 остатков равны 8.

[Ktina]

hippie
Супер!

Обычно называют число 8400, дающее 23 остатка, потому и было два вопроса.

[rockclimber]

Ktina в сообщении #1084262 писал(а):

Обычно называют число 8400, дающее 23 остатка

Они просто не знают SQL

Используется синтаксис SQL

WITH d1 AS (SELECT rownum  + 999 n FROM dual CONNECT BY level <= 9000),
     d2 AS (SELECT rownum + 1 n FROM dual CONNECT BY level <= 100)
SELECT n1, COUNT(*) cnt
  FROM (SELECT d1.n n1, d2.n n2, MOD(d1.n, d2.n) m
          FROM d1, d2
         WHERE MOD(d1.n, d2.n) = 8)
 GROUP BY n1
 ORDER BY cnt DESC

Используется синтаксис SQL

        N1        CNT
---------- ----------
      5048         26
      7928         25
      7568         25
      9248         24
      6308         23
      9368         23
      7208         23
      2528         23
      8408         23
 

P. S. Вы наверно хотели сказать 8408?

[Aritaborian]

Они просто не знают Wolfram Language

Reverse[SortBy[Select[Table[{n, Count[Mod[n, #] & /@ Range[2, 101], 8]}, {n, 1000, 9999}], (Last[#] >= 20) &], Last]]

rockclimber в сообщении #1084441 писал(а):

Вы наверно хотели сказать 8408?

Наверняка, да

[arseniiv]

(Оффтоп)

Они просто не имеют в подвале похищеного гениального вычислителя. Ой.

-- Пн дек 21, 2015 21:28:21 --

А вообще,

Используется синтаксис Haskell

-- GHCi
> let valueCountModulo n a = length . filter (== a) . map (n `mod`)
> let op `over` part x y = (part x) `op` (part y)
> import Data.List
> take 10 $ sortBy (flip (compare `over` snd)) [(n, valueCountModulo n 8 [2..101]) | n <- [1000..9999]]
[(5048,26),(7568,25),(7928,25),(9248,24),(2528,23),(6308,23),(7208,23),(8408,23),(9368,23),(3968,22)]

Или вот так: http://try.ceylon-lang.org/?gist=6aefbf0a2e94a1a8b3d0

// Ceylon (но так там не пишут) web runner

Integer valueCountModulo(Integer n, Integer a, {Integer*} ms) =>
    {for (m in ms) n % m}.count((v) => v == a);

printAll([for (n in 1000..9999) [n, valueCountModulo(n, 8, 2..101)]].sort((a, b) => b[1] <=> a[1]).take(10));

// [5048, 26], [7928, 25], [7568, 25], [9248, 24], [9368, 23], [8408, 23], [7208, 23], [6308, 23], [2528, 23], [9908, 22]

[NT2000]

rockclimber в сообщении #1084441 писал(а):

Они просто не знают SQL

Для тех кто знает SQL, но не имеет его под рукой
Поскольку представленные конструкции написаны для среды ORACLE SQL Design,
то дополню вашу информацию ссылкой на онлайн ORACLE терминал.

Может кому-то и пригодится.

[rockclimber]

NT2000 в сообщении #1084615 писал(а):

rockclimber в сообщении #1084441 писал(а):

Они просто не знают SQL

Для тех кто знает SQL, но не имеет его под рукой
Поскольку представленные конструкции написаны для среды ORACLE SQL Design,

Если выразиться точнее, то не "для среды ORACLE SQL Design", а для Oracle Database версий наверно 8 и выше А для онлайн выполнения запросов мне гораздо больше нравится sqlfiddle.com. Там и выбор СУБД большой, и таблички можно создавать с данными.

[NT2000]

О да, SQL Fiddle - значительно лучше

PS. я его раньше видел, но об опции выбора типа базы даже не подозревал.

[Vladimir-80]

А аналитически подобные задачи решаются? Или только перебором?

[rockclimber]

Должны решаться, но я в этом никогда не был силен. Сейчас первое, что пришло в голову: обозначим искомое число как $N$, тогда число $N - 8$ должно делиться нацело на как можно больше чисел в диапазоне от $9$ до $101$ (числа $8$ и меньше можно не рассматривать, так как при делении на них остаток всегда будет меньше восьми). То есть это число должно разлагаться на максимально большое количество простых делителей. Но при этом есть ограничение сверху, поэтому надо выбирать число, которое будет являться комбинацией преимущественно множителей 2, 3 и 5 (каковым и является упомянутое выше $8400$ - видимо, его таким способом проще всего найти). А вот доказать для какого-то числа, что оно дает максимальный результат, я наверно не смогу.

-- 23.12.2015, 02:07 --

Забавно, число-лидер - $5048$, а $5040$ - это $8!$ То есть факториал - это, похоже, способ получить небольшое число с большим разнообразием делителей (возможно, что и наименьшее число с наибольшим разнообразием).