Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 4 |
[ Сообщений: 32 ] | На страницу 1, 2, 3, 4 След. |
|
Автор | Сообщение | |
---|---|---|
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, опять добавляю, и т.д. Вроде все правильно, но нужный результат не получается. |
||
Вернуться к началу | ||
bimol |
|
|
Выбрасываем 100 и результат можно подогнать под максимум
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
Выбросил 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] |
||
Вернуться к началу | ||
bimol |
|
|
-100 - 19 + 95 + 64 = + 40 ?
|
||
Вернуться к началу | ||
ivashenko |
|
|
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 раз. |
||
Вернуться к началу | ||
s_e_r_g |
|
|
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 |
||
Вернуться к началу | ||
s_e_r_g |
|
|
ivashenko писал(а): Исключите 99, добавьте 64 и 81. Похоже всегда должны содержаться все простые плюс последние несколько квадратов, возможно 2 последние квадрата. Нет , 64 и 100 не являются взаимно простыми |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Нашел 1355
[1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99] |
||
Вернуться к началу | ||
ivashenko |
|
|
s_e_r_g писал(а): Нашел 1355 [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. |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Нашел 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 |
||
Вернуться к началу | ||
За это сообщение пользователю s_e_r_g "Спасибо" сказали: bimol |
||
На страницу 1, 2, 3, 4 След. | [ Сообщений: 32 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Конструкция бесконечного множества взаимно простых чисел
в форуме Теория чисел |
0 |
283 |
11 апр 2019, 09:52 |
|
Множество простых чисел и пар простых чисел-близнецов бескон
в форуме Размышления по поводу и без |
2 |
256 |
28 июн 2023, 11:23 |
|
Максимальное количество различных простых множителей
в форуме Теория чисел |
4 |
335 |
17 янв 2020, 13:14 |
|
Суммы взаимно простых | 11 |
844 |
27 апр 2015, 03:59 |
|
Суммы взаимно простых ч. 2 | 1 |
292 |
27 апр 2015, 21:31 |
|
Помощь с доказательством свойства взаимно простых многочлено
в форуме Линейная и Абстрактная алгебра |
4 |
157 |
19 май 2022, 22:06 |
|
Дан массив целых чисел. Найти максимальное число. Сделать в
в форуме Информатика и Компьютерные науки |
0 |
641 |
29 июн 2014, 14:02 |
|
Формула для простых чисел
в форуме Размышления по поводу и без |
30 |
1343 |
22 авг 2019, 23:30 |
|
Формула простых чисел
в форуме Теория чисел |
4 |
721 |
15 июл 2016, 08:01 |
|
Сумма простых чисел | 15 |
222 |
28 янв 2024, 10:52 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |