Задача о числах мудрецов

05.10.17

Разработка - Математика и алгоритмы

Решаем головоломку средствами 1С

Однажды мне попалась вот такая задача:

Пусть x и y два целых числа 1<x<y притом x + y≤100. Салли сказали только сумму x + y, а вот Полю произведение xy. Салли и Пол честнейшие ребята, это всем известно, они и друг другу отродясь не врали.
И вот такой вышел у них разговор:
Пол: «Не знаю я, что это за числа.»
Салли: «Тоже новость. Я знаю, что ты не знаешь.»
Пол: «Ну твоя то сумма мне теперь известна.»
Салли: «Да уж и мне теперь твое произведение.»
Каковы числа? 

Идея решения пришла быстро, но отыскать его с помощью бумаги и карандаша оказалось трудно, поэтому пришлось обратиться к 1С.

Сначала определим алгоритм поиска. Хочу поблагодарить Сергея (ildarovich) за сделанное замечание, это позволило исправить первоначальный вариант, который давал правильные решения, но содержал ошибку

На предварительном этапе с помощью функции GetSallySum получим числа из заданного диапазона, которые нельзя представить в виде :

  • суммы двух простых чисел;
  • суммы простого числа и его квадрата;
  • суммы простого числа и его куба.

При выполнении  данной операции используется вспомогательная функция EratosthenesSieve для генерации списка простых чисел с помощью алгоритма "решето Эратосфена" Вот исходный код:

function  EratosthenesSieve(Ulimit)
	
	vt=new array(Ulimit+1);
	for i=2 to  Ulimit do
		if vt[i]=undefined then
			vt[i]=true;
			j=i+i;
			while j<=Ulimit do
				vt[j]=false;	
	
	arr=new array;
	for i=2 to  Ulimit do
		if vt[i]=true then
			arr.Add(i);
		endif;
	enddo;
	
	return arr;
	
endfunction	


function GetSallySum(ULimit)
	
	notsally=new array;
    //в массив parr записываем все простые числа непревосходящие установленную границу
	parr=EratosthenesSieve(Ulimit);
	

	vt=new valuetable;
	vt.Columns.Add("i",new ОписаниеТипов("Число"));
	imax=parr.UBound();
	for  i=0 to imax  do
		for j=i to imax do
			s=parr[i]+parr[j];
			if s<ULimit then
				row=vt.add();
				row.i=s;
			endif;
		enddo;	
		
		s=parr[i]+parr[i]*parr[i];
		if s<ULimit then
			row=vt.add();
			row.i=s;
		endif;
		
		s=parr[i]+parr[i]*parr[i]*parr[i];
		if s<ULimit then
			row=vt.add();
			row.i=s;
		endif;
	enddo;	
	
	vt.GroupBy("i");
	notsally=vt.ВыгрузитьКолонку("i");
	
	
	sally=new array;
	for s=4 to ULimit do
		
		if notsally.Find(s)=undefined then
			 sally.Add(s);
		endif;
    enddo;		
	
	
	return sally;
endfunction	

На следующем шаге мы готовим таблицу с числами кандидатами, среди которых будет искаться решение. Сумма этих чисел равна числу из массива, который возвращает предыдущая функция. Вот фрагмент кода:

 vt=new valuetable;
 vt.columns.Add("i",new ОписаниеТипов("Число"));	
 vt.columns.Add("j",new ОписаниеТипов("Число"));		
 vt.columns.Add("Multij",new ОписаниеТипов("Число"));		
 vt.columns.Add("Sumij",new ОписаниеТипов("Число"));		
 
 arr=GetSallySum(UpLimit);	
 for each sally in arr do
	 for i=2 to (sally-sally%2)/2 do
		 row=vt.Add();
		 row.i=i;
		 row.j=sally-i;
		 row.Sumij=sally;
		 row.Multij=row.i*row.j;
	 enddo;	 
 enddo;	 

Теперь разберем структуру запроса. Временная таблица Candidate содержит исходные пары чисел, с рассчитанными для них значениями  суммы и произведения. В таблице GroupMult мы собираем неповторяющиеся значения произведений. Затем из исходных данных отбираем только те строки, которые содержат уникальное значение произведения. Среди найденных строк находим неповторяющиеся значения для суммы. А затем применяем найденные значения, как фильтр к предыдущей выборке.

Приведу код, который я использовал при поиске решения. Сначала текст вспомогательной функции, которая помещает таблицу значений во временную таблицу, чтобы появилась возможность обращаться к ней в запросе. Аргумент МТТ - это ссылка на объект типа МенеджерВременныхТаблиц.

Функция PutToTemporaryTable(vt,name,MTT)
    ТекстЗапроса="ВЫБРАТЬ
                 |    ВходнаяТаблица.*
                 |ПОМЕСТИТЬ ВременнаяТаблица
                 |ИЗ
                 |    &мТЗ КАК ВходнаяТаблица
                 |;";
                    
    запрос=новый Запрос;
    запрос.Параметры.Вставить("мТЗ",vt);
    запрос.текст=СтрЗаменить(ТекстЗапроса,"ВременнаяТаблица",name);
    запрос.TempTablesManager=MTT;
    запрос.Выполнить();

КонецФункции
 

Теперь функция, в которой реализован приведенный выше алгоритм.

function NumberOfSages() export
	
 TTM=new МенеджерВременныхТаблиц;	
	
 vt=new valuetable;
 vt.columns.Add("i",new ОписаниеТипов("Число"));	
 vt.columns.Add("j",new ОписаниеТипов("Число"));		
 vt.columns.Add("Multij",new ОписаниеТипов("Число"));		
 vt.columns.Add("Sumij",new ОписаниеТипов("Число"));		
 
 arr=GetSallySum(UpLimit);	
 for each sally in arr do
	 for i=2 to (sally-sally%2)/2 do
		 row=vt.Add();
		 row.i=i;
		 row.j=sally-i;
		 row.Sumij=sally;
		 row.Multij=row.i*row.j;
	 enddo;	 
 enddo;	 
 PutToTemporaryTable(vt,"Candidate",TTM);
 
 
 query=new query;
 query.МенеджерВременныхТаблиц=TTM;
 
 query.Текст="ВЫБРАТЬ
             |	Candidate.Multij КАК Multij
             |ПОМЕСТИТЬ GroupMult
             |ИЗ
             |	Candidate КАК Candidate
             |
             |СГРУППИРОВАТЬ ПО
             |	Candidate.Multij
             |
             |ИМЕЮЩИЕ
             |	КОЛИЧЕСТВО(*) = 1
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	Candidate.i КАК i,
             |	Candidate.j КАК j,
             |	Candidate.Multij КАК Multij,
             |	Candidate.Sumij КАК Sumij
             |ПОМЕСТИТЬ FilterMult
             |ИЗ
             |	Candidate КАК Candidate
             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ GroupMult КАК GroupMult
             |		ПО Candidate.Multij = GroupMult.Multij
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	FilterMult.Sumij КАК Sumij
             |ПОМЕСТИТЬ GroupSum
             |ИЗ
             |	FilterMult КАК FilterMult
             |
             |СГРУППИРОВАТЬ ПО
             |	FilterMult.Sumij
             |
             |ИМЕЮЩИЕ
             |	КОЛИЧЕСТВО(*) = 1
             |;
             |
             |////////////////////////////////////////////////////////////////////////////////
             |ВЫБРАТЬ
             |	FilterMult.i КАК i,
             |	FilterMult.j КАК j,
             |	FilterMult.Multij КАК Multij,
             |	FilterMult.Sumij КАК Sumij
             |ИЗ
             |	FilterMult КАК FilterMult
             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ GroupSum КАК GroupSum
             |		ПО FilterMult.Sumij = GroupSum.Sumij
             |
             |УПОРЯДОЧИТЬ ПО
             |	Sumij,
             |	Multij";
 
 
  query.Parameters.Insert("UpLimit",UpLimit);
 
  vt=query.Execute().UnLoad();
  
  return vt;
  
EndFunction	

Ответ приводить не буду. Приведу результаты своих исследований. В условиях задачи сумма чисел меньше или равна 37. Первое решение появляется, когда верхний предел становится равен 65. Второе решение появляется при верхнем пределе 439.

Послесловие.

В начале статьи я благодарю Сергея (ildarovich) за сделанное замечание. Он указал, что два различных числа больше единицы  однозначно определяются по их произведению не только в случае, когда эти числа простые, но и в двух других, когда их произведение является либо кубом либо четвертой степенью простого числа. Во всех найденных мной в Сети решениях задачи о мудрецах говорится только о произведении простых чисел. Впрочем, с таким заявлением я поспешил, в этой статье такие варианты рассматриваются. Проведем поиск решения на конкретном примере . И так у нас есть таблица, которая содержит суммы двух чисел и их произведение. Значения произведений мы можем разбить на две группы, в первую отнесем  повторяющиеся значения, во вторую неповторяющиеся.

Таблица с данными
На приведенном рисунке в левой таблице содержатся неповторяющиеся произведения, в правой повторяющиеся. Данные построены для случая, когда сумма сомножителей меньше или равна 11. Внимательный читатель сразу заметит, что к неповторяющимся отнесено произведение 20, хотя 20 равно 4*5 и 2*10. Точно так же не подходят под критерий неповторяющихся произведения 28 и 30. Все дело в ограничении на сумму.  Для числа 20 сумма множителей 4 и 5 равна 9 и эта пара попадает в исследуемый набор, а сумма множителей 2 и 10 равна 12, что больше верхнего предела. Поэтому эта пара в наборе отсутствует.  Отсюда первый вывод , то куда попадет произведение из исходной последовательности зависит от ограничения на сумму сомножителей.

Разбиение на 2 множества при ограничении на сумму 16

Если мы будем рассматривать набор чисел, для которых сумма множителей меньше 16, то увидим что значения 20,28 и 30 исчезли из левой таблицы. Это подтверждают данные на приведенном рисунке. Следующий шаг заключается в поиске таких значений из колонки Сумма, которые не встречаются в левой таблице, но присутствуют в правой. В последнем примере таким числом является 11. И обнаружить мы это можем только начиная с суммы множителей равной 16.  Вот и второе наблюдение, список чисел, которые не выражаются в виде суммы сомножителей, чье произведение не повторяется в рассматриваемом наборе, зависит от размера этого набора. Ниже приведен список таких чисел. В колонке Предел проставлено значения верхнего предела суммы множителей, при котором появляется данное значение. Такие суммы назовем числами Салли.

Таблица сумм

Решения нашей задачи нам нужно искать среди таких пар, у которых значение суммы содержится в приведенном выше наборе. Найденные пары опять разобьем на две группу. В первую занесем те значения, которые не содержат повторяющиеся значения из колонки Произведение, во вторую отнесем пары с повторяющимися значениями произведения. Ниже приводятся таблицы для случая, когда сумма множителей меньше 64.

Сумма меньше 64

Левая таблица показана не полностью. Обратим внимание на две пары из левой таблицы - (17;52) и (17;70). Увеличим верхнюю границу до 65. Согласно нашим данным при этом ограничении появляется число Салли равное 37.

Решение для верхней границы 65

37 можно представить в виде суммы двух чисел 2 и 35. Их произведение равно 70. Значит произведение со значением 70 стало повторяющимся, появилось две пары (17;70) и (37;70). Поэтому пара (17;70) из левой таблицы уйдет. И в левой таблице появится пара (17;52) , у которой значение из колонки Сумма уникальное. И эта пара будет первым решением  задачи о числах мудрецов.

В изложенном подходе мы обрабатывали исключительно набор данных образованных парами, составленными из значений суммы и произведения двух множителей. В этом случае состав множества чисел, которые мы назвали числа Салли, определяется верхней границей для суммы сомножителей. В тоже время, существует альтернативный подход для построения чисел Салли. На первом шаге мы можем сгенерировать ряд простых чисел. На следующем  составить множество из попарной суммы простых чисел и сумм вида (p+p*p), а также (p+p*p*p), где p - это простое число. А затем найти числа, которые не вошли в указанный набор, но больше его нижней границы и меньше верхней. Именно такой подход я использовал. Результаты, которые дает запрос Сергея (ildarovich) и подход с использованием генерации чисел Салли совпадают. Отличие заключается в значении суммы множителей, при которых эти решения появляются. Ниже приводится ряд образованный значениями ограничений на сумму, при которых появляются новые решения задачи, если использовать генератор чисел Салли - 37,439,757,991,1267,1925,2023,2227,2323.  Запрос Сергея дает первое решение при верхней границе - 65 (это показано в разобранном примере) , второе при верхней границе 1685.

Ну и наконец, заключительная таблица с числами мудрецов.

       число А              число В           Сумма      Произведение
4 13 17 52
4 61 65 244
16 73 89 168
16 111 127 1 776
64 73 137 4 672
32 131 163 4 192
4 229 233 916
32 311 343 9 952
64 309 373 19 776

Математика головоломки

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4420    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7464    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8839    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7806    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. itvdonsk 06.02.15 05:34 Сейчас в теме
И всего-то в задаче не указано что числа простые. Кажется автор телепат 80 уровня.
PheelSAV; GreenDragon; mrmasson; Dmirily; +4 Ответить
5. scientes 288 06.02.15 10:32 Сейчас в теме
(1) itvdonsk, Я прочитал замечание о простых числах и внес изменение в текст статьи, чтобы этот момент сразу стал понятен.
2. DoctorRoza 06.02.15 08:37 Сейчас в теме
Решать головоломки с помощью 1С - мое нутро отвергает это напрочь! Только хардкор, только С++/Java! :)
3. monkbest 115 06.02.15 10:02 Сейчас в теме
Не очень понятно, почему это обязательно простые числа?
4. Alien_job 190 06.02.15 10:25 Сейчас в теме
конечно не простые, автор об этом пишет в первом же абзаце
6. Alien_job 190 06.02.15 10:59 Сейчас в теме
7. scientes 288 06.02.15 11:28 Сейчас в теме
(6) Alien_job, если будет желание поэкспериментируйте со значением ограничения на сумму. Первое решение появится только тогда, когда верхняя граница равна 37, хотя сумма чисел решения будет меньше этого значения. 4 и 61 тоже самое, я сначала думал, что это ошибка в моей программе. Но нет, так и должно быть.
11. Alien_job 190 06.02.15 11:35 Сейчас в теме
(7) да, экспериментирую. Но не представляю причину отсутствия решения при ограничении на сумму ммм меньше 37
12. Alien_job 190 06.02.15 11:44 Сейчас в теме
(7) "Среди строк таблицы есть такие, которые содержат уникальные значения в колонке сумма или произведение, например, произведение простых чисел будет уникальным. Такие данные нам надо удалить." Почему вы удаляете уникальные произведения?
13. scientes 288 06.02.15 11:59 Сейчас в теме
(12) Alien_job, ни Пол, ни Салли не знают решение. Значит известные им значения суммы и произведения не позволяют назвать числа. Поэтому варианты с уникальными значениями мы и удаляем. Скажем, если бы Полу назвали произведение 143, он разложил его на множители 11 и 13. Это разложение единственное, он сразу называет ответ.
8. davealone 165 06.02.15 11:31 Сейчас в теме
Допустим мы отсеяли все простые, но дальше если сумма и произведение известны, почему не решить головоломку как систему уравнений? Есть:
X + Y = SUM -> Y = SUM - X
X * Y = PROD - > SUM*X - X^2 = PROD -> X^2 - SUM*X + PROD = 0
Получим обычное квадратное уравнение, у которого меньший корень єто X, а больший Y
9. Alien_job 190 06.02.15 11:33 Сейчас в теме
(8) davealone, мы не знаем суммы и произведения
10. Alien_job 190 06.02.15 11:33 Сейчас в теме
(8) davealone, мы не знаем суммы и произведения(7)
14. Идальго 226 06.02.15 17:24 Сейчас в теме
Если числа непростые, то рассмотрим давайте пару (4, 15). Так, Салли сказали сумму = 19, ну и Полу = 60. Понятно, что Пол не знает из каких двух множетелей получается сложное число 60, веть это может быть пара (2, 30) или (3, 20) или (4, 15) или (5, 12) или (6, 10). От того, знает/не знает Салли, что Пол не знает пару этих чисел - ничего не меняется. Да и сам Салли на самом деле не знает из каких слагаемых образовалась сумма = 19. Поэтому, я думаю чего-то не хватает в условии. Хотя может и ошибаюсь?
15. ildarovich 7850 06.02.15 23:45 Сейчас в теме
Не знаю, где я ошибся, но вот решение, которое никак не хочет второй вариант на 439 показывать. Это всего один запрос и более короткий, чем у автора. Работает в консоли.
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Бит

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Бит0.Х + 2 * (Бит1.Х + 2 * (Бит2.Х + 2 * (Бит3.Х + 2 * (Бит4.Х + 2 * (Бит5.Х + 2 * (Бит6.Х + 2 * (Бит7.Х + 2 * (Бит8.Х + 2 * Бит9.Х)))))))) КАК Х
ПОМЕСТИТЬ Ряд
ИЗ
	Бит КАК Бит9,
	Бит КАК Бит8,
	Бит КАК Бит7,
	Бит КАК Бит6,
	Бит КАК Бит5,
	Бит КАК Бит4,
	Бит КАК Бит3,
	Бит КАК Бит2,
	Бит КАК Бит1,
	Бит КАК Бит0
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Ряд1.Х КАК Х,
	Ряд2.Х КАК У,
	Ряд1.Х + Ряд2.Х КАК Сумма,
	Ряд1.Х * Ряд2.Х КАК ХУ
ПОМЕСТИТЬ Пробы
ИЗ
	Ряд КАК Ряд1,
	Ряд КАК Ряд2
ГДЕ
	Ряд1.Х < &Предел / 2
	И Ряд2.Х < &Предел - 1
	И 1 < Ряд1.Х
	И Ряд1.Х < Ряд2.Х
	И Ряд1.Х + Ряд2.Х <= &Предел
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Пробы.Сумма
ПОМЕСТИТЬ ТабуСумм
ИЗ
	Пробы КАК Пробы
ГДЕ
	Пробы.ХУ В
			(ВЫБРАТЬ
				Пробы.ХУ
			ИЗ
				Пробы КАК Пробы
			СГРУППИРОВАТЬ ПО
						Пробы.ХУ
			ИМЕЮЩИЕ
				КОЛИЧЕСТВО(*) = 1)
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.ХУ
ПОМЕСТИТЬ ЧислаПоля
ИЗ
	Пробы КАК ЧислаСалли
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.ХУ

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаСалли.Сумма) = 1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ЧислаСалли.Сумма,
	МАКСИМУМ(ЧислаПоля.ХУ) КАК Произведение,
	МАКСИМУМ(ЧислаСалли.Х) КАК Х,
	МАКСИМУМ(ЧислаСалли.У) КАК У
ИЗ
	Пробы КАК ЧислаСалли
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЧислаПоля КАК ЧислаПоля
		ПО ЧислаСалли.ХУ = ЧислаПоля.ХУ
ГДЕ
	НЕ ЧислаСалли.Сумма В
				(ВЫБРАТЬ
					ТабуСумм.Сумма
				ИЗ
					ТабуСумм)

СГРУППИРОВАТЬ ПО
	ЧислаСалли.Сумма

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ЧислаПоля.ХУ) = 1
Показать
А возможно, ошибки и нет, а ошибка в исходной статье? Дело в том, что предположение про простые числа - не совсем верное. Вот, например 8 разлагается на сомножители однозначно, но не является произведением двух простых чисел.
16. Sykoku 101 11.02.15 11:36 Сейчас в теме
Я думал, что решали ЛОГИЧЕСКУЮ задачу про мудрецов в колпаках (http://eruditor.ru/z/?2). А тут...

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

Решать арифметические задачи методом подбора - это еще додуматься надо...
17. scientes 288 11.02.15 11:54 Сейчас в теме
(16) Sykoku, Я полагаю, что это не арифметическая задача. Ответ получается в результате выполнения запроса. В Послесловии разобрано как этот запрос работает. Все методы решения, которые я видел, в той или иной форме реализуют этот алгоритм.
18. пользователь 03.01.18 21:00
Сообщение было скрыто модератором.
...
Оставьте свое сообщение