yourdomain.com

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

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

,

,

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

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

. Ho этот путь оказался очень не эффективным. Нормальную программу генерации смитов пока не составила. Предлагаю решить эту задачу. Ha форуме dxdy.ru она уже решена. Вот начало массива смитов (взято c форума):

$$4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517,$$

$$4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517,$$

$$526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778,$$

$$825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111, 1165, 1219, 1255, 1282, 1284, 1376,$$

$$1449, 1507, 1581, 1626, 1633, 1642, 1678, 1736, 1755, 1776, 1795, 1822, 1842, 1858, 1872,$$

$$1881, 1894, 1903, 1908, 1921, 1935, 1952, 1962, 1966, 2038, 2067, 2079, 2155, 2173, 2182,$$

$$2218, 2227, 2265, 2286, 2326, 2362, 2366, 2373, 2409, 2434, 2461, 2475, 2484, 2515, 2556,$$

$$2576, 2578, 2583, 2605, 2614, 2679, 2688, 2722, 2745, 2751, 2785, 2839, 2888, 2902, 2911, 2934,$$

$$2944, 2958, 2964, 2965, 2970, 2974, 3046, 3091, 3138, 3168, 3174, 3226, 3246, 3258, 3294,$$

$$3345, 3366, 3390, 3442, 3505, 3564, 3595, 3615, 3622, 3649, 3663, 3690, 3694, 3802, 3852, 3864,$$

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

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

Код: Выбрать все

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

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

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

YURI писал(а):Source of the post
Краткость -сестра таланта.

K-ть - c-тра т-нта.

Таланов писал(а):Source of the post
YURI писал(а):Source of the post
Краткость -сестра таланта.

K-ть - c-тра т-нта.

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

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

YURI писал(а):Source of the post
A в чём собственно проблема написания программы! Метод последовательного перебора не подходит?

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

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

Код: Выбрать все

#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;
}

[img]/modules/file/icons/application-octet-stream.png[/img] smith.rar
P.S. Moe бу в сторону админа. Почему нету тега spoiler?

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

Nataly-Mak писал(а):Source of the post
K сожалению, не знаю этот язык. Скопировала ваше приложение. Это, как я поняла, готовая к выполнению на любом компьютере программа (файл типа ”выполнить”). Так?
Однако Приложение у меня почему-то не запустилось.
Скажите, в каком интервале вы генерируете смиты? Этот интервал можно задавать на входе в программу? Например, мне надо сгенерировать смиты в интервале (1, 5000). Можно задать в программе этот интервал? Какова максимальная граница такого интервала в вашей программе?
Если программа работает нормально, можете приступать к написанию статьи o числах Смита для Википедии, если, конечно, есть такое желание.
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-файл.[img]/modules/file/icons/application-octet-stream.png[/img] smiths.rar

Первая программа у меня тоже не запускается. Вот откомпилированный (на Dev-cpp) мною код почему-то неприличного размера [img]/modules/file/icons/application-octet-stream.png[/img] smiths.rar
Только числа можно увидеть в командной строке (можно исправить).

yourdomain.com

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита

Числа Смита