Числа Смита, интересное множество чисел Опции

[Nataly-Mak]

(По материалам статьи ”Замечательные смиты” (журнал ”Наука и жизнь”, № 3, 2009 г.; автор Н. Карпушина) и Научного форума dxdy.ru: http://dxdy.ru/topic12959.html ).

Жил на свете наблюдательный профессор психологии Гарольд Смит и был у него телефон с таким номером: 4937775. Однажды Смит случайно заметил интересное свойство своего телефонного номера: сумма цифр этого числа равна сумме цифр его простых делителей.
, ,

Быть может, этот факт так и остался бы в разряде числовых курьёзов, не вмешайся в историю родственник Смита — математик, профессор одного из американских университетов Альберт Виланский. Он опубликовал в 1982 году заметку об обнаруженном свойстве, а обладающие им составные числа назвал именем Смита. Тогда же Виланский предположил, что таких чисел существует бесконечно много. И оказался прав: вскоре эту гипотезу доказал его коллега. Так было положено начало исследованию весьма интересного множества чисел.

В связи с этими интересными числами сразу же возникло множество интересных задач. Ну, учитывая специфику моих интересов, большинство задач у меня связаны с магическими квадратами. Сразу же начала предлагать эти задачи на форуме dxdy.ru. Там уже столько задач решено!
Первая интересная задача связана с составлением программы генерации смитов. Я начала искать смиты сначала путём умножения простых чисел на . Но этот путь оказался очень не эффективным. Нормальную программу генерации смитов пока не составила. Предлагаю решить эту задачу. На форуме dxdy.ru она уже решена. Вот начало массива cмитов (взято с форума):







Далее интересны задачи нахождения арифметических прогрессий разной длины из смитов (из таких прогрессий элементарно строятся магические квадраты). На форуме найдены прогрессии длиной 9, 10, 11, 12, 13. Пока можно из найденных прогрессий составить только магические квадраты 3-го порядка из разных смитов. Если удастся найти прогрессию длиной 16, тогда можно будет построить магический квадрат 4-го порядка.

Построение нетрадиционных магических квадратов из смитов – моя самая важная задача. На форуме построен магический квадрат 4-го порядка (квадрат 3-го порядка приведён в указанной статье журнала ”Наука и жизнь”) с минимальной магической константой 1195. Я составила программу построения нетрадиционных магических квадратов 4-го порядка (её можно использовать для построения квадратов из простых чисел, для построения квадратов из смитов; я даже использовала её для построения всех диагональных классических латинских квадратов 4-го порядка).
Теперь такая задача: надо построить четыре квадрата 4-го порядка из смитов с одинаковой магической константой, но из разных чисел (ни одно число во всех 4-х квадратах не должно повторяться). Затем очень просто сложить из этих четырёх квадратов нетрадиционный магический квадрат 8-го порядка из разных смитов.
Эта задача на форуме dxdy.ru решена. Пользователь, решивший задачу, предложил её в Project Euler. Поэтому просьба к тем, кто решит эту задачу: не публикуйте пока её решение. Если задача будет принята в проекте, тогда пошлёте туда своё решение.
Ну, понятно, что можно аналогично попробовать построить магический квадрат 12-го порядка из разных смитов. Для этого надо найти девять квадратов 4-го порядка с одинаковой магической константой, но из разных чисел (впрочем, можно и с разными магическими константами, если из этих констант сложится магический квадрат 3х3). Эта задача ещё никем не решена.
Для примера приведу нетрадиционный магический квадрат 8-го порядка, составленный из 4-х квадратов 4х4 с одинаковой магической константой (1276), но с повторяющимися числами:

Код

22 454 535 265 85 355 634 202
274 382 58 562 391 274 94 517
346 319 517 94 346 526 382 22
634 121 166 355 454 121 166 535
121 346 274 535 778 166 274 58
634 319 58 265 94 22 265 895
355 517 382 22 85 634 355 202
166 94 562 454 319 454 382 121

Все четыре квадрата я построила по своей программе.
У вас должен получиться подобный квадрат, но все числа в нём должны быть разные. Я пока эту задачу не решила.
Следующая нерешённая задача – построение магического квадрата 5-го порядка из разных смитов с минимальной магической константой.
***
Творческая задача – написать статью в Википедию о числах Смита. В английской Википедии такая статья есть
http://en.wikipedia.org/wiki/Smith_number
а вот в русской Википедии нет. Но прежде чем писать эту статью, надо сделать программу генерации смитов, без неё не стоит затевать статью.

Сообщение отредактировал Nataly-Mak - 27.7.2009, 3:47

[YURI]

Краткость -сестра таланта.

[talanov]

Краткость -сестра таланта.

К-ть - с-тра т-нта.

Сообщение отредактировал talanov - 25.7.2009, 16:26

[Nataly-Mak]

Краткость -сестра таланта.

К-ть - с-тра т-нта.

Господа, вам не кажется, что это флуд?
Может, вы ошиблись темой?
А не посмотреть ли вам для начала, сколько на эту тему написано на форуме dxdy.ru?
А-а-а! Дошло! Вы больше трёх строк читать не можете.

Сообщение отредактировал Nataly-Mak - 25.7.2009, 18:35

[YURI]

А в чём собственно проблема написания программы! Метод последовательного перебора не подходит?

[Nataly-Mak]

А в чём собственно проблема написания программы! Метод последовательного перебора не подходит?

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

[12d3]

Программка во вложении. Любые пожелания по ее улучшению приветствуются.
Если что, ее код на С++.

Код

#include <iostream>
#include <cmath>
using namespace std;

int summa_cifr(int n) {
    int i = 0;
    while (n) {
        i += n % 10;
        n /= 10;
    }
    return i;
}

int main() {
    int i,j,n,sum1,sum2,k;
    bool flag;
    cout<<"Enter max number ";
    cin>>n;
    for (int i = 2; i <= n; i++) {
        flag=false;
        sum1 = summa_cifr(i);
        sum2 = 0;
        k = i;
        j = 2;
        while (j <= sqrt((double)k)) {
            if (k % j == 0) {
                sum2 += summa_cifr(j);
                k /= j;
                flag = true;
            } else
                j++;
        }
        sum2 += summa_cifr(k);
        if (sum1 == sum2 && flag)
            cout<<i<<endl;
    }
    cin>>i;
    return 0;
}

 smith.rar ( 9.81 килобайт ) Кол-во скачиваний: 26

P.S. Мое бу в сторону админа. Почему нету тега spoiler?

Сообщение отредактировал 12d3 - 26.7.2009, 7:01

[Nataly-Mak]

К сожалению, не знаю этот язык. Скопировала ваше приложение. Это, как я поняла, готовая к выполнению на любом компьютере программа (файл типа ”выполнить”). Так?
Однако Приложение у меня почему-то не запустилось.
Скажите, в каком интервале вы генерируете смиты? Этот интервал можно задавать на входе в программу? Например, мне надо сгенерировать смиты в интервале (1, 5000). Можно задать в программе этот интервал? Какова максимальная граница такого интервала в вашей программе?
Если программа работает нормально, можете приступать к написанию статьи о числах Смита для Википедии, если, конечно, есть такое желание.
P.S. Вы протестировали программу, сверяясь с приведённым здесь массивом смитов?

Сообщение отредактировал Nataly-Mak - 27.7.2009, 3:49

[YURI]

К сожалению, не знаю этот язык. Скопировала ваше приложение. Это, как я поняла, готовая к выполнению на любом компьютере программа (файл типа ”выполнить”). Так?
Однако Приложение у меня почему-то не запустилось.
Скажите, в каком интервале вы генерируете смиты? Этот интервал можно задавать на входе в программу? Например, мне надо сгенерировать смиты в интервале (1, 5000). Можно задать в программе этот интервал? Какова максимальная граница такого интервала в вашей программе?
Если программа работает нормально, можете приступать к написанию статьи о числах Смита для Википедии, если, конечно, есть такое желание.
P.S. Вы протестировали программу, сверяясь с приведённым здесь массивом смитов?

Выкладываю свою программу на CИ. Естественно её можно улучшить (сам вижу способы, но в первом приближении пойдёт).

Код

#include<stdio.h>
#include<math.h>

int dsum(int);
int testprime(int);
int primedsum(int);

int main(void)
{
    int i, n;
    FILE *fout; fout=fopen("Smith_nums.txt","w");
    printf("Enter n:"); scanf("%d", &n);
    for(i=2;i<n;i++) if(testprime(i)==1) i++; else {
    if(dsum(i)==primedsum(i)) fprintf(fout,"%d, ",i);}
    fclose(fout);
return 0;    
}

int dsum(int n)
{   int sum=0;
    while (n!=0)
    {
        sum += n%10;
        n/= 10;
    }
    return sum;
}

int testprime(int p)
{
    int i=2;
while(i<=sqrt(p))
{
if(p%i==0) break; else i++;    
}
p=sqrt(p)+1;

if(i==p) return 1; else return 0;
}

int primedsum(int n)
{   int sum=0, k=2;
    for(k=2;k<=n;k++) {if(testprime(k)==1) for(;n%k==0;n/=k) sum+=dsum(k);}
    return sum;
}

При запуске исполняемого файла вводите число, меньше которого нужно генерировать смиты. Числа записываются в создающийся txt-файл.  smiths.rar ( 4.58 килобайт ) Кол-во скачиваний: 25

[YURI]

Первая программа у меня тоже не запускается. Вот откомпилированный (на Dev-cpp) мною код почему-то неприличного размера  smiths.rar ( 103.98 килобайт ) Кол-во скачиваний: 26

Только числа можно увидеть в командной строке (можно исправить).

[12d3]

Сейчас программа считает быстро (до 10 миллионов примерно полминуты), но жрет много памяти, примерно 10 Мб на каждый миллион проверяемых чисел. Все выводится в файл.
Теперь надо заморочиться с поиском прогрессий.
 smith.rar ( 166.51 килобайт ) Кол-во скачиваний: 28

[YURI]

Сейчас программа считает быстро (до 10 миллионов примерно полминуты), но жрет много памяти, примерно 10 Мб на каждый миллион проверяемых чисел. Все выводится в файл.
Теперь надо заморочиться с поиском прогрессий.
 smith.rar ( 166.51 килобайт ) Кол-во скачиваний: 28

Да работает гораздо быстрее, чем моя. А можно код посмотреть??

[Nataly-Mak]

Сейчас программа считает быстро (до 10 миллионов примерно полминуты), но жрет много памяти, примерно 10 Мб на каждый миллион проверяемых чисел. Все выводится в файл.
Теперь надо заморочиться с поиском прогрессий.
 smith.rar ( 166.51 килобайт ) Кол-во скачиваний: 28

Значит, можно воскликнуть: "Есть генератор смитов!" Ура!
Прежде чем начинать искать прогрессии, обязательно посмотрите тему "Магические квадраты" на форуме dxdy.ru
http://dxdy.ru/topic12959.html
Там уже многое сделано, найдены прогрессии до 13 членов включительно. Но числа при этом получаются громадные (сотни миллионов).

Сообщение отредактировал Nataly-Mak - 27.7.2009, 11:49

[12d3]

А можно код посмотреть??

Конечно. Идея - решето Эратосфена.

Код

#include <fstream>
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;

int summa_cifr(int n) {
    int i = 0;
    while (n) {
        i += n % 10;
        n /= 10;
    }
    return i;
}

vector <int> prev,sums,smiths;

void generate_smiths(int n) {
    prev.resize(n+1);
    sums.resize(n+1);
    for (int i=0; i<prev.size();i++) prev[i]=0;
    for (int i=2;i<=n;i++) {
        if (!prev[i]) {
            sums[i]=summa_cifr(i);
            for (int j=2;j<=n/i;j++)
                prev[j*i]=i;
        } else {
            sums[i]=sums[prev[i]]+sums[i/prev[i]];
            if (sums[i] == summa_cifr(i))
                smiths.push_back(i);
        }
    }
}

int main() {
    ofstream fout("smith.txt");
    int n;
    cout<<"Enter n ";
    cin>>n;
    if (n<=100000000) {
        generate_smiths(n);
    }else
        cout<<"Number is too big";
    for (int i=0;i<smiths.size();i++) fout<<smiths[i]<<endl;
    return 0;
}

[YURI]

Сейчас программа считает быстро (до 10 миллионов примерно полминуты), но жрет много памяти, примерно 10 Мб на каждый миллион проверяемых чисел. Все выводится в файл.
Теперь надо заморочиться с поиском прогрессий.
 smith.rar ( 166.51 килобайт ) Кол-во скачиваний: 28

Значит, можно воскликнуть: "Есть генератор смитов!" Ура!
Прежде чем начинать искать прогрессии, обязательно посмотрите тему "Магические квадраты" на форуме dxdy.ru
http://dxdy.ru/topic12959.html
Там уже многое сделано, найдены прогрессии до 13 членов включительно. Но числа при этом получаются громадные (сотни миллионов).

Простите, а какой интерес в таких обрубленных недопрогрессиях? Гораздо интересней например чисто теоретические вопросы
1) Существует ли прогрессии из смитов.
2) Сущ ли смиты вида n, n+1 и т.д

[Nataly-Mak]

Простите, а какой интерес в таких обрубленных недопрогрессиях? Гораздо интересней например чисто теоретические вопросы
1) Существует ли прогрессии из смитов.
2) Сущ ли смиты вида n, n+1 и т.д

Что значит "обрубленных"? Вы хотите сказать, что можно найти "необрубленную", то есть бесконечную арифметическую прогрессию из смитов? Вряд ли!
Ответ на вопрос № 1 положительный: арифметические прогрессии из смитов существуют, и они уже найдены. Ответ на второй вопрос тоже положительный, например, два рядом стоящих смита - . Думаю, что таких много.
У меня нужда в арифметических прогрессиях из смитов толька одна - из таких прогрессий элементарно строятся магические квадраты. Есть ли ещё какая польза от таких прогрессий, я не знаю. Как, впрочем, и от арифметических прогрессий из простых чисел, коих найдено уже немало, но максимальная длина в найденных арифметических прогрессиях из простых чисел - 25, длиннее не найдено. Числа там астрономические (на форуме dxdy.ru дана ссылка на прогрессии из простых чисел). Я построила несколько магических квадратов с помощью этих прогрессий (4-го и 5-го порядков). Кстати, доказано, что для простых чисел существуют арифметические прогрессии любой длины.
Если вам нравится заниматься теоретическими исследованиями чисел Смита, пожалуйста. Кто против?

Сообщение отредактировал Nataly-Mak - 27.7.2009, 12:55

[YURI]

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

Нет, я хочу узнать истину. "А вряд ли" - не аргумент.

Ответ на вопрос № 1 положительный: арифметические прогрессии из смитов существуют, и они уже найдены.

Вот опять. Я имею ввиду последовательность, а не обрубки

Ответ на второй вопрос тоже положительный, например, два рядом стоящих смита - .

Единственная польза в ваших словах




Кстати вначале я подумал, что простые - тоже смиты.

[Nataly-Mak]

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

Нет, я хочу узнать истину. "А вряд ли" - не аргумент.

Хотите узнать истину? Похвально! Узнайте! Я эту истину не знаю, но предполагаю, что бесконечной арифметической прогрессии из смитов не существует. Докажите обратное!
Сейчас проверила вашу программу. Всё работает. Правда, ещё не сверила выдаваемый массив смитов.

[YURI]

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

Нет, я хочу узнать истину. "А вряд ли" - не аргумент.

Хотите узнать истину? Похвально! Узнайте! Я эту истину не знаю, но предполагаю, что бесконечной арифметической прогрессии из смитов не существует. Докажите обратное!
Сейчас проверила вашу программу. Всё работает. Правда, ещё не сверила выдаваемый массив смитов.

Из простых бесконечной прогрессии, очевидно, не существует. Для смитов интересно выяснить существует ли сколь угодно большой промежуток без смитов, если нет - то каков максимальный?

[Nataly-Mak]

YURI, я выполнила вашу программу, введя в неё . Программа отработала довольно быстро. Я начала сверять массив выданных смитов с массивом, приведённым здесь (этот массив был получен на форуме dxdy.ru очень опытным товарищем). В вашем массиве нет таких смитов: 588, 648, 654, 728, 762, 1284, 1872. Дальше я не стала проверять. Может быть, у меня что-то не так с вашей программой?
Сейчас проверю вторую программу (другого товарища).
Ещё раз обращаю ваше внимание на то, что программу надо протестировать. Массив смитов здесь ведь не просто так приведён (не ради длинного сообщения).