Ох и ни фига себе!

[spamsink]

Оказывается, что с помощью чисел от 1 до 9, четырех арифметических действий и скобок можно выразить все числа от 1 до 3253.

Это я один скриптик на работе в пятницу вечером запустил, а убить забыл.

Upd: Даже без деления - до 22 тысяч с лишним. Дальше пока не знаю.

Comments

[gmz.livejournal.com]

Без скобок?

[gmz.livejournal.com]

Совсем тупой стал, читаю через два слова.

через два слова

[cema.livejournal.com]

А начиная с какого?

Re: через два слова

[gmz.livejournal.com]

:-) с правой скобки

[cema.livejournal.com]

А 3254?

[spamsink]

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

[cema.livejournal.com]

В каком смысле случайным поиском?

[spamsink]

Да в прямом. Shuffle, pop, pop, apply random op, push, shuffle, pop, pop, apply random op, push, ... Более эффективный поиск за несколько минут пока дал первое непредставимое значение 3265, а всего из первых 10000 чисел нашлось 8872.

[spamsink]

И 3265 отставить. Пока 3493.

[kdv2005.livejournal.com]

А статистика распределения ответов есть? Насколько равномерно такой алгоритм покрывает числовую ось?

[spamsink]

Статистику не собирал, хотя вопрос, чему равно ожидаемое значение случайного арифметического выражения описанного вида, тоже интересен. Максимум, очевидно, равен 1.5*9!.

После того, как я переписал скрипт с перла на C++, дело пошло гораздо быстрее. Пока из первых 10000 не покрыты остались всего 2 числа: 7759 и 9623.

[kdv2005.livejournal.com]

Не исключено, что само распределение будет очень неравномерным и будут ответы, которые встречаются чаще других в такой случайной последовательности арифметических действий. Кстати, а почему нуля нет? Чтобы избежать проблем с делением?

[spamsink]

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

[cartesius.livejournal.com]

А числа при этом могут быть использованы несколько раз?

[spamsink]

Нет, каждое ровно по одному разу.

[russian-o.livejournal.com]

А вы не пробовали поискать информацию? Может, эту задачу уже в общем виде решили, т.е. доказали как теорему, что это возможно для любого числа? Интересно просто.

[spamsink]

Знать бы, как искать. По "pandigital expression" находится преимущественно старая задачка, как сделать 100 или 1000 из цифр от 1 до 9, и они там обычно позволяют себе делать из цифр многозначные числа.

[russian-o.livejournal.com]

Это надо профессионального математика спрашивать. Возможно, данная задача это частный случай какой-нибудь теоремы. Только вот как это понять? :-)

[le-xa.livejournal.com]

Можно попробовать задать вопрос в ru_math

[cartesius.livejournal.com]

Если числа не повторяются, то максимальное число, которое можно выразить при таком условии: 544 320 = (1+2)*3*4*5*6*7*8*9

[spamsink]

Разумеется. Мне интересно, чему равно минимальное число, которое нельзя выразить.