2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Числа в ряд и целое число процентов
Сообщение11.01.2019, 00:55 
Аватара пользователя


01/12/11

8634
Можно ли поставить в ряд все натуральные числа от 1 до 100 так, чтобы каждые два соседних числа отличались на целое число процентов (проценты можно брать от любого из двух сравниваемых чисел, по желанию)?

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 10:00 


05/09/16
12061
Ktina
Похоже, что нет.
Для десяти последних простых чисел $53,59,61,67,71,73,79,83,89,97$ парами (стоять слева или справа) могут быть только девять чисел $1,2,4,5,10,20,25,50,100$ и кажись из-за этого полный ряд всех чисел не составить.

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 11:10 
Аватара пользователя


01/12/11

8634
wrest
Любопытно, что для чисел от 1 до 10 это легко сделать: 7, 1, 2, 3, 4, 5, 6, 8, 10, 9. Напрашивается обобщение задачи - для каких наборов чисел от 1 до $n$ это можно сделать?

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 11:25 


05/09/16
12061
Ktina в сообщении #1367647 писал(а):
Любопытно, что для чисел от 1 до 10 это легко сделать:

Ну тут же два параметра: сколько чисел, и как округлять. Вернее не округлять, а на что умножать чтобы получилось целое -- в исходном посте вы предлагаете умножать на $2 \cdot 2 \cdot 5 \cdot 5 =100$ (как раз и добавляя ко всем простым в пару все делители сотни, т.е. $2,4,5,10,20,25,50,100$). А для чисел $1-10$ предлагаете тоже умножать на $100$? :wink:
Впрочем, первую десятку чисел можно расставить и по целым десяткам процентов, вроде.

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 11:34 
Аватара пользователя


01/12/11

8634
wrest в сообщении #1367658 писал(а):
Ну тут же два параметра: сколько чисел, и как округлять. Вернее не округлять, а на что умножать чтобы получилось целое -- в исходном посте вы предлагаете умножать на $2 \cdot 2 \cdot 5 \cdot 5 =100$ (как раз и добавляя ко всем простым в пару все делители сотни, т.е. $2,4,5,10,20,25,50,100$). А для чисел $1-10$ предлагаете тоже умножать на $100$? :wink:
Впрочем, первую десятку чисел можно расставить и по целым десяткам процентов, вроде.

Извините, мне совсем непонятен Ваш вопрос. Зачем на что-то умножать? Число 1, например, отличается от числа 7 на 600 процентов, если проценты брать от числа 1.

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 11:54 


05/09/16
12061
Ktina в сообщении #1367661 писал(а):
Извините, мне совсем непонятен Ваш вопрос. Зачем на что-то умножать? Число 1, например, отличается от числа 7 на 600 процентов, если проценты брать от числа 1.

А как вы вычисляете на сколько процентов одно число больше другого?
Эти ваши $600$ процентов для чисел $a=1;b=7$ получаются так: $\Delta = |(1-b/a)\cdot 100|$

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 12:00 
Аватара пользователя


01/12/11

8634
wrest
Верно!
В таком случае, какая разница, сколько чисел изначально дано?

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 12:07 


05/09/16
12061
Ktina в сообщении #1367669 писал(а):
В таком случае, какая разница, сколько чисел изначально дано?

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

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 13:25 


05/09/16
12061
Как модификацию - я бы предложил такую: имеются числа от 1 до 100, какой максимальной длины можно составить ряд из них такой, что соседние числа отличаются на целое число процентов?

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 16:16 
Аватара пользователя


01/12/11

8634
wrest в сообщении #1367682 писал(а):
Как модификацию - я бы предложил такую: имеются числа от 1 до 100, какой максимальной длины можно составить ряд из них такой, что соседние числа отличаются на целое число процентов?

Ваше предложение принято!

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 17:00 


05/09/16
12061
Ktina в сообщении #1367760 писал(а):
Ваше предложение принято!

Ну тогда вот вам функция PARI/GP для тестирования подходят ли числа (принимает два числа, возвращает 1 если подходят и 0 если не подходят):
Цитата:
intproc(x,y)=if(denominator((1-x/y)*100)==1,return(1));if(denominator((1-y/x)*100)==1,return(1));return(0)

и функция, которая принимает на вход ряд чисел и проверяет подходящий ли это ряд:
Цитата:
testproc(v)=for(i=1,#v-1,if(!intproc(v[i],v[i+1]), return(0)));return(1)

Запуск (обратите внимание -- числа для тестирования ряда надо вводить в квадратных скобках внутри круглых скобок):
? intproc(2,3)
%1 = 1
? intproc(3,7)
%2 = 0
? testproc([1,2,3])
%3 = 1
? testproc([1,2,3,7])
%4 = 0
?

Проверка на повтор чисел в ряду не производится

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 17:31 
Аватара пользователя


01/12/11

8634
wrest
Большое спасибо!

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 17:38 
Заслуженный участник
Аватара пользователя


16/07/14
9149
Цюрих
wrest в сообщении #1367770 писал(а):
Ну тогда вот вам функция PARI/GP для тестирования подходят ли числа (принимает два числа, возвращает 1 если подходят и 0 если не подходят):
Цитата:
intproc(x,y)=if(denominator((1-x/y)*100)==1,return(1));if(denominator((1-y/x)*100)==1,return(1));return(0)

Неужели в PARI/GP нет остатка от деления? В известных мне языках проверка пишется так: x * 100 % y == 0 || y * 100 % x == 0.
(а задача о последовательности максимальной длины - это в точности longest path для некоторого графа; его вроде бы умеют решать для таких размеров, но сходу я солвера не нашел, а в терминах MIP оно плохо переформулируется)

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 17:42 
Супермодератор
Аватара пользователя


20/11/12
5728
mihaild в сообщении #1367786 писал(а):
Неужели в PARI/GP нет остатка от деления?
Есть конечно: Mod

 Профиль  
                  
 
 Re: Числа в ряд и целое число процентов
Сообщение11.01.2019, 17:50 


05/09/16
12061
mihaild в сообщении #1367786 писал(а):
Неужели в PARI/GP нет остатка от деления?
Есть.
mihaild в сообщении #1367786 писал(а):
пишется так: x * 100 % y == 0 || y * 100 % x == 0
Да, синтаксис точно такой же. То есть функцию можно переписать как
Код:
intproc(x,y)=x * 100 % y == 0 || y * 100 % x == 0

Не знаю, правда, как оно вычисляет "или" -- до конца или до первой единицы.

Denominator показалось мне красивым и понятным. :mrgreen:
Дело ещё в том, что рациональные числа PARI/GP хранит как несократимую дробь в виде двух чисел -- числителя и знаменателя, поэтому denominator -- это просто извлечение знаменателя.
Ну и плюс, запись как у меня мне кажется человечнее :lol:

...хотя и с процентами красиво смотрится, да. Спасибо!

-- 11.01.2019, 17:57 --

mihaild в сообщении #1367786 писал(а):
а в терминах MIP оно плохо переформулируется

А что там надо в качестве исходных данных?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модератор: Модераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group