Числа в ряд и целое число процентов

[Ktina]

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

[wrest]

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

[Ktina]

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

[wrest]

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

Любопытно, что для чисел от 1 до 10 это легко сделать:

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

[Ktina]

wrest в сообщении #1367658 писал(а):

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

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

[wrest]

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

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

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

[Ktina]

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

[wrest]

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

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

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

[wrest]

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

[Ktina]

wrest в сообщении #1367682 писал(а):

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

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

[wrest]

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
?
Проверка на повтор чисел в ряду не производится

[Ktina]

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

[mihaild]

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 оно плохо переформулируется)

[Deggial]

mihaild в сообщении #1367786 писал(а):

Неужели в PARI/GP нет остатка от деления?

Есть конечно: Mod

[wrest]

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 показалось мне красивым и понятным.
Дело ещё в том, что рациональные числа PARI/GP хранит как несократимую дробь в виде двух чисел -- числителя и знаменателя, поэтому denominator -- это просто извлечение знаменателя.
Ну и плюс, запись как у меня мне кажется человечнее

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

-- 11.01.2019, 17:57 --

mihaild в сообщении #1367786 писал(а):

а в терминах MIP оно плохо переформулируется

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