Ярденифицированные числа

[Ktina]

Назовём натуральное число ярденифицированным, если его можно разложить на двузначные натуральные множители.

а) Докажите, что из миллиарда ярденифицированных чисел всегда можно выбрать два, произведение которых является точным квадратом.

б) Насколько мощным может быть множество ярденифицированных чисел, если известно, что никакие два из них не образуют точный квадрат при их перемножении?

[arseniiv]

а) Простых чисел меньше ста 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 всего 26 штук. Либо в разложение я. числа на простые входит нечётное число множителей такого вида, либо чётное, и входит чётное число всех остальных простых. Всего вариантов чётности-нечётности $2^{26} = 67108864 < 10^9$, так что какой-то вариант будет реализован как минимум дважды, вот два таких числа и перемножаем, получая точный квадрат. Задача подобного вида уже была на форуме в этом или прошлом месяце.

б) Соответственно, максимум 67108864 числа.

Простовато.

[Ktina]

arseniiv
Большое спасибо, только простых чисел, меньших 100, не 26, а 25.

[arseniiv]

Ой. Сначала правильно насчитал 25, а потом пересчитал и получил 26. Но раз 26 влезает, 25 и подавно.

[Ktina]

arseniiv
А пример на максимум разве столь очевиден? Там же и однозначные простые попадаются, надо их как-то одвузначить.

[arseniiv]

А, и правда, оценка может быть не самой лучшей. Снимаю б).

-- Пн янв 22, 2018 02:14:50 --

Его можно воскресить, если верно следующее. Определим уже точно для числа $n$ «профиль чётности простых» $[n]$ как вектор пространства $\mathbb F_2^\omega$ последовательностей из нулей и единиц, соответствующих степеням (по модулю 2) простых в разложении $n$. Тогда если линейная оболочка $\{[n] : n\in10..99\}$ равна-таки $\{[n] : n\in2..99\}$, всё прекрасно. Иначе говоря, $[2],[3],[5],[7]$ должны быть выразимы линейными комбинациями из $[10],\ldots,[99]$. Скорее всего это так.

[mihaild]

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

надо их как-то одвузначить

А просто когда мы хотим множители $2,3,5,7$ брать вместо них $32,12,20,28$ не сойдет?

[arseniiv]

$[32] = 5[2] = [2]$, $[12] = [3]$, $[20] = [5]$, $[28] = [7]$, mihaild поставил точку.