Можно ли определить, когда будет найдено число?

@ronaldo · Регистрация: 16.06.2014

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Есть задача:
Найти минимальное число, большее заданного, которое равно сумме своих десятичных цифр, возведённой в степень, большую 1.
Например, если вводится 2000, то искомым будет число 2401.
Например, если вводится 1000000000, то искомым будет число 8303765625.
Предвидя отрицательный ответ, тем не менее, спрашиваю: можно ли, имея лишь заданное число, определить некое число, меньше которого точно будет искомое число?

@kabenyuk · 01.04.2015, 08:00

ronaldo, требуется по числу а определить такое число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b]. При этом само с можно не вычислять. Так?

@ronaldo · 01.04.2015, 11:14 **[ТС]**

kabenyuk, почти. Следующая формулировка точнее:
Требуется по числу а определить такое минимальное число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b].

c не вычислять - в том и фишка.

Байт · 01.04.2015, 12:54

Сообщение от ronaldo

минимальное число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b].
c не вычислять - в том и фишка.

Имхо, тут логическое противоречие. Поскольку минимальным таким b и будет это c.
Точнее, b - минимальное число, большее a, являющееся некоторой степенью суммы своих цифр.
Наверное, нужно найти хоть какое нибудь b, ограничивающее область поиска? Нет?

@chumich · 01.04.2015, 13:43

ronaldo, вот программа, которая находит все числа в промежутке от 11 до 1 000 000 000, которые можно представить через возведение в степень суммы их цифр.

C#

            Console.Write("поиск чисел");
            for (int n = 11; n <1000000000; n++)
            {
                int sum = 0;
                int num = n;
                while (num != 0)
                {
                    sum += num % 10;
                    num /= 10;
                }       
                for (int g = 0; g < 10; g++)
                {
                    if (Math.Pow(sum, g) == n)
                    {
                        Console.Write("\n" + n);
                    }
                }
            }
            Console.Write("\nпоиск окончен");
            Console.Read();

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

@kabenyuk · 01.04.2015, 13:58

Сообщение от ronaldo

Требуется по числу а определить такое минимальное число b,

Все-таки правильнее сказать так "минимально возможное". Но я не об этом.
Не знаю для чего вам это нужно. Но вот учитывать проще сумму цифр и степень.
Например, 199²⁰=1887620149539230539058375534310517606114631604199.
Сумма цифр монстра в правой части (числом назвать его язык не поворачивается) равна 199
(если я нигде не ошибся). С другой стороны, слева совершенно безобидные малютки 199 и 20.

Добавлено через 14 минут
Небольшая опечатка. Степень 199 должна быть 21.

@ronaldo · 01.04.2015, 14:51 **[ТС]**

Байт, вы правы.

Сообщение от kabenyuk

Но вот учитывать проще сумму цифр и степень.

Извиняюсь за тупость, но не понял этой фразы. Учитывать где?

Кстати, kabenyuk, как вы такое замечательное равенство получили?

Байт · 01.04.2015, 15:05

Видимо, речь идет о том, что программу, ищущую такие числа, можно построить так.
Перебирать числа x и степени y. У числа x^y считать сумму цифр s. И если s=x, кричать Ура!
Перебор будет значительно короче. Легче воспользоваться длинной арифметикой ("длинных" операций меньше, всего лишь умножение на короткое) и значит легко пойти дальше машинного представления (и по дороге получить монстра kabenyuk).
Но у этой задачи возможно обобщение. Зачем останавливаться только на десятичной системе счисления?

@kabenyuk · 01.04.2015, 15:09

Сообщение от ronaldo

Извиняюсь за тупость, но не понял этой фразы. Учитывать где?

Да я тоже не понимаю и не знаю, где.

Сообщение от ronaldo

Кстати, как вы такое замечательное равенство получили?

У меня таких много. Байт секрет раскрыл. Но пользовался только excel'ем.

Байт · 01.04.2015, 15:31

Вот симпатичное число в 2-ичной 1010001 = 11⁴

Добавлено через 4 минуты

Сообщение от kabenyuk

Но пользовался только excel'ем.

И до какого порядка excel числа может считать?
Насколько я знаю, сам по себе Excel с такими не работает (впрочем, могу и ошибаться, я не большой знаток). Наверное, какое-то хитрое представление, да?

Добавлено через 14 минут
Вот, кстати, неплохой алгоритм.
Найти число, удовлетворяющее условию
Но только для чисел, представимых в стандартных типах.

Байт · 01.04.2015, 17:38

Вот, сделал маленькую программуленьку (Си)
Числа получаются любопытные, приятно посмотреть...

@ronaldo · 01.04.2015, 18:08 **[ТС]**

Байт, можете идею из восьмого поста применить для решения задачи:
Найти минимальное число, большее заданного, которое равно сумме своих десятичных цифр, возведённой в степень, большую 1.
Я ходил по ссылке из десятого поста, но мне интересна реализация именно вами описанного алгоритма.

@kabenyuk · 01.04.2015, 18:30

Сообщение от Байт

И до какого порядка excel числа может считать?

Ну если не позаботиться, то не более 10 десятичных цифр. Понятно, что необходимо использовать что-то типа длинной арифметики + VBA. Да, и умножать короткие на длинные, которые удобно представлять как текстовые строки десятичного представления числа.

@chumich · 01.04.2015, 18:34

Сообщение от ronaldo

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

ronaldo, я вам в программе приведенной выше вроде бы уже реализовал эту идею. Нужно только заменить тип данных, чтобы считать числа больше 1 000 000 000, вместо n = 11 ставить начало перебора с заданного числа и сделать выход из цикла при нахождении первого значения

.

Байт · 01.04.2015, 19:20

Сообщение от kabenyuk

Да, и умножать короткие на длинные, которые удобно представлять как текстовые строки десятичного представления числа.

Я, собственно, так и поступил во вложении поста 11. Но немножко схитрил в целях эффективности. Я представляю числа в 1000-ичной системе. Можно было бы взять систему по максимуму short, это дало бы еще больший выигрыш в эффективности, но тогда замучаешься в десятичную переводить (хотя тоже - не Бином Ньютона). И эффективность на этом переводе терялась бы.

Добавлено через 14 минут

Сообщение от chumich

я вам в программе приведенной выше

При всем уважении к вашим стараниям, хочу заметить, что предложенный вами алгоритм крайне не эффективен для достаточно больших чисел. Мало того, что вы перебираете все числа, так еще и все возможные степени! Даже для представимых в стандартных типах чисел (до 10⁹, скажем) он будет работать неоправдано долго. Что уж говорить о "длинных" числах.

Добавлено через 8 минут

Сообщение от ronaldo

можете идею из восьмого поста применить для решения задачи:

Вам ведь нужно именно минимальное, да?
Собственно, генерацию таких чисел я уже реализовал в посте 11 (вложение). Но они генерируются "вразброс". Как найти минимальное? Ничего умнее, чем сравнивать и выбирать меньшее, в голову не приходит. Но где остановиться? В какой момент будет ясно, что меньше уже не получится?
И еще вопрос. С числами какого порядка вы собираетесь работать? Помещающимися в стандартные типы, или нужно чего-то большего?

Добавлено через 16 минут
Попутно хочу похвастаться. Число

Сообщение от kabenyuk

1887620149539230539058375534310517606114631604199.

может сложить с себя звание монстра

900 pow 217 = 117 658 836 200 566 641 882 326 804 988 437 726 931 934 010 014 963 224 628 533 621 567 999 100 883 880 584 910 085 936 271 537 026 481 185 458 945 323 393 439 742 082 113 315 251 718 144 829 436 251 273 438 085 673 551 344 210 424 446 349 697 811 909 784 006 141 340 373 856 900 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
(Разбил на триады для внятности)

@ronaldo · 01.04.2015, 19:47 **[ТС]**

Сообщение от Байт

Вам ведь нужно именно минимальное, да?

Да.

Сообщение от Байт

С числами какого порядка вы собираетесь работать? Помещающимися в стандартные типы, или нужно чего-то большего?

У заданного числа тип должен быть unsigned __int64.

Я в вашем коде (X.C) разбираюсь - какой тип у newXXL, nulXXL, locXXL, addXXL? void?

Байт · 01.04.2015, 20:22

Сообщение от ronaldo

какой тип у newXXL, nulXXL, locXXL, addXXL? void?

Да. Старые компиляторы допускали некоторые вольности...

Добавлено через 31 минуту

Сообщение от ronaldo

У заданного числа тип должен быть unsigned __int64.

Но результат может быть и больше, да?
На всякий случай набросал пару функций

C

void Int64ToXXL(unsigned __int64 I, XXL *x)  // Перевод int64 => XXL
{
   newXXL(x);
   for(; I; I /= 1000) addXXL(x, I%1000);
}
int cmpXXL(XXL *x, XXL *y)  // Сравнение
{
   if (x->ns != y->ns) return x->ns - y->ns;
   for(int i=x->ns-1; i>=0; i--)
     if ((k = x->ss[i] - y->ss[i])) return k;
   return 0;
}

И еще маленький вопрос. Эта задача существует сама по себе? Или является частью другой?

@ronaldo · 01.04.2015, 20:40 **[ТС]**

Сообщение от Байт

Но результат может быть и больше, да?

Логично предположить, что да.

Сообщение от Байт

На всякий случай набросал пару функций

Но я ведь могу просто в коде из поста 11 заменить SU на unsigned __int64?

Сообщение от Байт

Эта задача существует сама по себе? Или является частью другой?

Задача-то сама по себе. А вот задание, состоящее в написании проги для этой задачи, на самом деле, состоит не только в написании проги для этой задачи (извиняюсь за тавтологию). Потом нужно будет распараллелить прогу с использованием технологий OpenMP.

Байт · 01.04.2015, 20:52

Сообщение от ronaldo

Но я ведь могу просто в коде из поста 11 заменить SU на unsigned __int64?

Попробуй.
Но там фишка в том, что они <1000. И программа при умножении за этим внимательно следит. Вообще, при работе с длинными числами каждый "разряд" должен быть немножко меньше максимально возможного. Ведь когда мы умножаем 9*6, у нас получается 54. В одной цифре мы этот результат удержать не можем. В цифрах у нас получается "4", а 5 - в уме (Vume). А то, что я делаю в X.C - это просто моделирование этой "школьной" арифметики.

Сообщение от ronaldo

Потом нужно будет распараллелить прогу с использованием технологий OpenMP.

Тут я тебе, к сожалению, не помощник...

@ronaldo · 01.04.2015, 21:22 **[ТС]**

Сообщение от Байт

Тут я тебе, к сожалению, не помощник...

Ты в этой теме помоги по максимуму, плиз.
Я думал над этим

Сообщение от Байт

Но где остановиться? В какой момент будет ясно, что меньше уже не получится?

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

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
		1
	Можно ли определить, когда будет найдено число? 01.04.2015, 04:47. Показов 1722. Ответов 31 Метки нет (Все метки) Доброго времени суток. Есть задача: Найти минимальное число, большее заданного, которое равно сумме своих десятичных цифр, возведённой в степень, большую 1. Например, если вводится 2000, то искомым будет число 2401. Например, если вводится 1000000000, то искомым будет число 8303765625. Предвидя отрицательный ответ, тем не менее, спрашиваю: можно ли, имея лишь заданное число, определить некое число, меньше которого точно будет искомое число? 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	01.04.2015, 08:00	2
	ronaldo, требуется по числу а определить такое число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b]. При этом само с можно не вычислять. Так? 1

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 11:14 [ТС]	3
	kabenyuk, почти. Следующая формулировка точнее: Требуется по числу а определить такое минимальное число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b]. c не вычислять - в том и фишка. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	01.04.2015, 12:54	4
	Сообщение от ronaldo минимальное число b, что число с, равное некоторой степени суммы своих десятичных цифр, находится в промежутке [a,b]. c не вычислять - в том и фишка. Имхо, тут логическое противоречие. Поскольку минимальным таким b и будет это c. Точнее, b - минимальное число, большее a, являющееся некоторой степенью суммы своих цифр. Наверное, нужно найти хоть какое нибудь b, ограничивающее область поиска? Нет? 1

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	01.04.2015, 13:58	6
	Сообщение от ronaldo Требуется по числу а определить такое минимальное число b, Все-таки правильнее сказать так "минимально возможное". Но я не об этом. Не знаю для чего вам это нужно. Но вот учитывать проще сумму цифр и степень. Например, 199²⁰=1887620149539230539058375534310517606114631604199. Сумма цифр монстра в правой части (числом назвать его язык не поворачивается) равна 199 (если я нигде не ошибся). С другой стороны, слева совершенно безобидные малютки 199 и 20. Добавлено через 14 минут Небольшая опечатка. Степень 199 должна быть 21. 2

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 14:51 [ТС]	7
	Байт, вы правы. Сообщение от kabenyuk Но вот учитывать проще сумму цифр и степень. Извиняюсь за тупость, но не понял этой фразы. Учитывать где? Кстати, kabenyuk, как вы такое замечательное равенство получили? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	01.04.2015, 15:05	8
	Видимо, речь идет о том, что программу, ищущую такие числа, можно построить так. Перебирать числа x и степени y. У числа x^y считать сумму цифр s. И если s=x, кричать Ура! Перебор будет значительно короче. Легче воспользоваться длинной арифметикой ("длинных" операций меньше, всего лишь умножение на короткое) и значит легко пойти дальше машинного представления (и по дороге получить монстра kabenyuk). Но у этой задачи возможно обобщение. Зачем останавливаться только на десятичной системе счисления? 1

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	01.04.2015, 15:09	9
	Сообщение от ronaldo Извиняюсь за тупость, но не понял этой фразы. Учитывать где? Да я тоже не понимаю и не знаю, где. Сообщение от ronaldo Кстати, как вы такое замечательное равенство получили? У меня таких много. Байт секрет раскрыл. Но пользовался только excel'ем. 2

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	01.04.2015, 15:31	10
	Вот симпатичное число в 2-ичной 1010001 = 11⁴ Добавлено через 4 минуты Сообщение от kabenyuk Но пользовался только excel'ем. И до какого порядка excel числа может считать? Насколько я знаю, сам по себе Excel с такими не работает (впрочем, могу и ошибаться, я не большой знаток). Наверное, какое-то хитрое представление, да? Добавлено через 14 минут Вот, кстати, неплохой алгоритм. Найти число, удовлетворяющее условию Но только для чисел, представимых в стандартных типах. 1

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 18:08 [ТС]	12
	Байт, можете идею из восьмого поста применить для решения задачи: Найти минимальное число, большее заданного, которое равно сумме своих десятичных цифр, возведённой в степень, большую 1. Я ходил по ссылке из десятого поста, но мне интересна реализация именно вами описанного алгоритма. 0

	01.04.2015, 21:22

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	01.04.2015, 18:30	13
	Сообщение от Байт И до какого порядка excel числа может считать? Ну если не позаботиться, то не более 10 десятичных цифр. Понятно, что необходимо использовать что-то типа длинной арифметики + VBA. Да, и умножать короткие на длинные, которые удобно представлять как текстовые строки десятичного представления числа. 1

@chumich 2080 / 1238 / 464 Регистрация: 20.12.2014 Сообщений: 3,237
	01.04.2015, 18:34	14
	Сообщение от ronaldo Байт, можете идею из восьмого поста применить для решения задачи: Найти минимальное число, большее заданного, которое равно сумме своих десятичных цифр, возведённой в степень, большую 1. ronaldo, я вам в программе приведенной выше вроде бы уже реализовал эту идею. Нужно только заменить тип данных, чтобы считать числа больше 1 000 000 000, вместо n = 11 ставить начало перебора с заданного числа и сделать выход из цикла при нахождении первого значения . 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	01.04.2015, 19:20	15
	Сообщение от kabenyuk Да, и умножать короткие на длинные, которые удобно представлять как текстовые строки десятичного представления числа. Я, собственно, так и поступил во вложении поста 11. Но немножко схитрил в целях эффективности. Я представляю числа в 1000-ичной системе. Можно было бы взять систему по максимуму short, это дало бы еще больший выигрыш в эффективности, но тогда замучаешься в десятичную переводить (хотя тоже - не Бином Ньютона). И эффективность на этом переводе терялась бы. Добавлено через 14 минут Сообщение от chumich я вам в программе приведенной выше При всем уважении к вашим стараниям, хочу заметить, что предложенный вами алгоритм крайне не эффективен для достаточно больших чисел. Мало того, что вы перебираете все числа, так еще и все возможные степени! Даже для представимых в стандартных типах чисел (до 10⁹, скажем) он будет работать неоправдано долго. Что уж говорить о "длинных" числах. Добавлено через 8 минут Сообщение от ronaldo можете идею из восьмого поста применить для решения задачи: Вам ведь нужно именно минимальное, да? Собственно, генерацию таких чисел я уже реализовал в посте 11 (вложение). Но они генерируются "вразброс". Как найти минимальное? Ничего умнее, чем сравнивать и выбирать меньшее, в голову не приходит. Но где остановиться? В какой момент будет ясно, что меньше уже не получится? И еще вопрос. С числами какого порядка вы собираетесь работать? Помещающимися в стандартные типы, или нужно чего-то большего? Добавлено через 16 минут Попутно хочу похвастаться. Число Сообщение от kabenyuk 1887620149539230539058375534310517606114631604199. может сложить с себя звание монстра 900 pow 217 = 117 658 836 200 566 641 882 326 804 988 437 726 931 934 010 014 963 224 628 533 621 567 999 100 883 880 584 910 085 936 271 537 026 481 185 458 945 323 393 439 742 082 113 315 251 718 144 829 436 251 273 438 085 673 551 344 210 424 446 349 697 811 909 784 006 141 340 373 856 900 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 (Разбил на триады для внятности) 4

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 19:47 [ТС]	16
	Сообщение от Байт Вам ведь нужно именно минимальное, да? Да. Сообщение от Байт С числами какого порядка вы собираетесь работать? Помещающимися в стандартные типы, или нужно чего-то большего? У заданного числа тип должен быть unsigned __int64. Я в вашем коде (X.C) разбираюсь - какой тип у newXXL, nulXXL, locXXL, addXXL? void? 0

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 20:40 [ТС]	18
	Сообщение от Байт Но результат может быть и больше, да? Логично предположить, что да. Сообщение от Байт На всякий случай набросал пару функций Но я ведь могу просто в коде из поста 11 заменить SU на unsigned __int64? Сообщение от Байт Эта задача существует сама по себе? Или является частью другой? Задача-то сама по себе. А вот задание, состоящее в написании проги для этой задачи, на самом деле, состоит не только в написании проги для этой задачи (извиняюсь за тавтологию). Потом нужно будет распараллелить прогу с использованием технологий OpenMP. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	01.04.2015, 20:52	19
	Сообщение от ronaldo Но я ведь могу просто в коде из поста 11 заменить SU на unsigned __int64? Попробуй. Но там фишка в том, что они <1000. И программа при умножении за этим внимательно следит. Вообще, при работе с длинными числами каждый "разряд" должен быть немножко меньше максимально возможного. Ведь когда мы умножаем 96, у нас получается 54. В одной цифре* мы этот результат удержать не можем. В цифрах у нас получается "4", а 5 - в уме (Vume). А то, что я делаю в X.C - это просто моделирование этой "школьной" арифметики. Сообщение от ronaldo Потом нужно будет распараллелить прогу с использованием технологий OpenMP. Тут я тебе, к сожалению, не помощник... 1

@ronaldo 94 / 48 / 63 Регистрация: 16.06.2014 Сообщений: 386
	01.04.2015, 21:22 [ТС]	20
	Сообщение от Байт Тут я тебе, к сожалению, не помощник... Ты в этой теме помоги по максимуму, плиз. Я думал над этим Сообщение от Байт Но где остановиться? В какой момент будет ясно, что меньше уже не получится? Вопросы, конечно, очень сложные. Единственное соображение в моей голове по этому поводу - когда найдём первое подходящее число (подходящее - большее заданного и находимое в твоей проге), то все последующие числа уже нужно будет возводить в степени, меньшие показателя степени подошедшего числа. 0