Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 21:41 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Задача описана тут:
http://euler.jakumo.org/problems/view/355.html

Дано число n. Найти максимально возможное по сумме множество взаимно простых чисел, меньших, чем n.
Например , для n=10 это множество будет равно {1, 5, 7, 8, 9}, сумма = 30
Для n=30 сумма равна 193, само множество - {1, 11, 13, 17, 19, 23, 25, 27, 28, 29}
Для n=100 сумма равна 1356, я пока не могу найти его, как ни странно
Все, что у меня получается - это сумма = 1310, а само множество -
[1, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99, 100]

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 22:19 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 17:51
Сообщений: 952
Cпасибо сказано: 154
Спасибо получено:
150 раз в 135 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
Выбрасываем 100 и результат можно подогнать под максимум

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 22:21 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Выбросил 100, получилось еще меньше:
1306 [1, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97, 98, 99]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 23:06 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 17:51
Сообщений: 952
Cпасибо сказано: 154
Спасибо получено:
150 раз в 135 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
-100 - 19 + 95 + 64 = + 40 ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 23:24 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
s_e_r_g писал(а):
Задача описана тут:
http://euler.jakumo.org/problems/view/355.html

Дано число n. Найти максимально возможное по сумме множество взаимно простых чисел, меньших, чем n.
Например , для n=10 это множество будет равно {1, 5, 7, 8, 9}, сумма = 30
Для n=30 сумма равна 193, само множество - {1, 11, 13, 17, 19, 23, 25, 27, 28, 29}
Для n=100 сумма равна 1356, я пока не могу найти его, как ни странно
Все, что у меня получается - это сумма = 1310, а само множество -
[1, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 99, 100]

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


Исключите 99, добавьте 64 и 81.
Похоже всегда должны содержаться все простые плюс последние несколько квадратов, возможно 2 последние квадрата.


Последний раз редактировалось ivashenko 19 фев 2016, 23:28, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 23:27 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
bimol писал(а):
-100 - 19 + 95 + 64 = + 40 ?


Почти в десятку:
1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 91, 97, 95, 99
Сумма = 1350

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 23:30 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
ivashenko писал(а):
Исключите 99, добавьте 64 и 81.
Похоже всегда должны содержаться все простые плюс последние несколько квадратов, возможно 2 последние квадрата.


Нет , 64 и 100 не являются взаимно простыми

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 19 фев 2016, 23:45 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Нашел 1355 :Search:
[1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 20 фев 2016, 00:08 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
s_e_r_g писал(а):
Нашел 1355 :Search:
[1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]

вместо 99 19+81
нет, снова ошибка, 95 кратно 19.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 20 фев 2016, 09:37 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Нашел 1356
[1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 88, 89, 91, 95, 97]

Не обошлось без рандомайзера
Когда я прибавляю справа к исходному массиву простых числа n, я делаю это не подряд, а в случайной последовательности

Непонятно, какой результат должен быть для n=1000

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю s_e_r_g "Спасибо" сказали:
bimol
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3, 4  След.  Страница 1 из 4 [ Сообщений: 32 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Конструкция бесконечного множества взаимно простых чисел

в форуме Теория чисел

AndrejVolkov

0

283

11 апр 2019, 09:52

Множество простых чисел и пар простых чисел-близнецов бескон

в форуме Размышления по поводу и без

korolchukvasily

2

256

28 июн 2023, 11:23

Максимальное количество различных простых множителей

в форуме Теория чисел

IvanPetrovPRO

4

335

17 янв 2020, 13:14

Суммы взаимно простых

в форуме Интересные задачи участников форума MHP

lopkityu

11

844

27 апр 2015, 03:59

Суммы взаимно простых ч. 2

в форуме Интересные задачи участников форума MHP

lopkityu

1

292

27 апр 2015, 21:31

Помощь с доказательством свойства взаимно простых многочлено

в форуме Линейная и Абстрактная алгебра

Mark17

4

157

19 май 2022, 22:06

Дан массив целых чисел. Найти максимальное число. Сделать в

в форуме Информатика и Компьютерные науки

Nesquik60

0

641

29 июн 2014, 14:02

Формула для простых чисел

в форуме Размышления по поводу и без

Tirpa

30

1343

22 авг 2019, 23:30

Формула простых чисел

в форуме Теория чисел

Xenobius

4

721

15 июл 2016, 08:01

Сумма простых чисел

в форуме Интересные задачи участников форума MHP

MurChik

15

222

28 янв 2024, 10:52


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved