2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Подмножества с целым средним геометрическим
Сообщение02.05.2017, 09:47 
Аватара пользователя


01/12/11

8634
Пусть у нас даны натуральные числа от 1 до $n$.
Назовём непустое подмножество множества этих чисел путным, если среднее геометрическое элементов этого подмножества является натуральным числом.
Как определить, чётно или нечётно количество путных подмножеств, в зависимости от $n$?

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение02.05.2017, 16:21 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Немудрёная програмулька (если я ничего не напутал)
Код:
goodSubsetQ[subset_] := IntegerQ[GeometricMean[subset]]
Table[Total[Boole[goodSubsetQ /@ Rest[Subsets[Range[i]]]]], {i, 1, 18}]
выдала количества путных подмножеств для $n=1...18$:
Код:
1, 2, 3, 6, 7, 8, 9, 12, 19, 20, 21, 28, 29, 30, 31, 40, 41, 70.
Кто-нибудь может подметить какую-либо закономерность?

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение02.05.2017, 17:20 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Aritaborian в сообщении #1213659 писал(а):
Кто-нибудь может подметить какую-либо закономерность?
Ну если нужна закономерность относительно вопроса задачи (чётное количество или нет), то я рискну заметить, что чётные и нечётные в этой последовательности строго чередуются :D

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение03.05.2017, 00:34 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Воспарив куда-то выше, этого я заприметить не пожелал :facepalm: BTW, дальше там $71$ и $74$.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение04.05.2017, 23:38 
Заслуженный участник


10/01/16
2318
Что то мне подумалось, что на 27-м шаге мы обломаемся. Но, насчитав в разности $a_{27} - a_{26}$ 40 элементов, как то не совсем не уверен в правильности подсчета....

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение05.05.2017, 00:25 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
Закономерность: номера членов, отличающихся от предыдущих больше чем на $1$ - в точности не свободные от квадратов числа.
А еще $f_n - n$ - это A147751 :D

-- 05.05.2017, 00:56 --

И даже понятно, почему так. Если максимальное число в подмножестве раскладывается как $t = p_1 \cdot \ldots \cdot p_n$ (числа не повторяются) и входит в состав $k$-элементного множества, то произведение остальных $k - 1$ членов этого множества не меньше чем $\prod p_i^{k-1}$, и хотя бы одно из них не меньше $t$.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение05.05.2017, 12:35 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
А, ясно. Последовательность, приведённая мною, включала тривиальные (одноэлементные) подмножества (и в OEIS никак не находилась), а эта не включает. OEIS приводит только для $n \leqslant 20$. Имеет ли смысл считать дальше? (Я посчитал до 23. Расчёты оч. долгие получаются, и постепенно больше и больше нагружают оперативку.)

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение05.05.2017, 15:52 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
Досчитал чуть дальше (без учета тривиальных)

(список)

  1. 0
  2. 0
  3. 0
  4. 2
  5. 2
  6. 2
  7. 2
  8. 4
  9. 10
  10. 10
  11. 10
  12. 16
  13. 16
  14. 16
  15. 16
  16. 24
  17. 24
  18. 52
  19. 52
  20. 54
  21. 54
  22. 54
  23. 54
  24. 84
  25. 98
  26. 98
  27. 184
  28. 186
  29. 186
  30. 186
  31. 186
  32. 300
  33. 300
  34. 300
  35. 300
  36. 556
  37. 556
  38. 556
  39. 556
  40. 572
  41. 572
  42. 572
  43. 572
  44. 574
  45. 594
  46. 594
  47. 594
  48. 1112
  49. 1134
  50. 1274

Если зачем-то нужно, можно посчитать дальше.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение05.05.2017, 16:38 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
mihaild, чем считали?

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение05.05.2017, 16:49 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
Руками. Чем еще?
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <map>
#include <array>
#include <iostream>
#include <utility>

const std::array<int, 6> PRIMES = {2, 3, 5, 7, 11, 13};//, 17, 19};//, 23, 29, 31, 37};

using TFactorization = std::array<int, PRIMES.size()>;
using TProfile = std::pair<int, TFactorization>;

TFactorization factorize(int n) {
    TFactorization result;
    for (auto &x : result) {
        x = 0;
    }
    for (size_t i = 0; i < PRIMES.size(); ++i) {
        while (n % PRIMES[i] == 0) {
            ++result[i];
            n /= PRIMES[i];
        }
    }
    if (n != 1) {
        throw std::exception();
    }
    return result;
}

int main() {
    int n;
    std::cin >> n;
    std::map<TProfile, int> data;
    int r = 0;
    data[{0, factorize(1)}] = 1;
    data[{1, factorize(1)}] = 1;
    //std::cout << "1: 1 ok" << std::endl;
    for (int i = 2; i <= n; ++i) {
        std::map<TProfile, int> next_data(data);
        bool ff = true;
        TFactorization factorization;
        try {
            factorization = factorize(i);
        } catch (...) {
            ff = false;
        }
        if (ff) {
            for (const auto& profile : data) {
                TProfile new_profile(profile.first);
                new_profile.first += 1;
                for (size_t i = 0; i < PRIMES.size(); ++i) {
                    new_profile.second[i] += factorization[i];
                }
                bool ok = new_profile.first > 1;
                for (size_t i = 0; i < PRIMES.size(); ++i) {
                    if (new_profile.second[i] % new_profile.first) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    r += profile.second;
                }
                next_data[new_profile] += profile.second;
            }
        }
        data = next_data;
        std::cout << '(' << i << " " << r << ')' << std::endl;
        std::cerr << '(' << i << " " << r << ')' << ' ' << data.size() << std::endl;
    }
    return 0;
}
 

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение06.05.2017, 09:19 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
И как, эти библиотеки быстро считают? Wolfram Mathematica для относительно больших $n$ считает часами. Это обратная сторона лёгкости написания кода, который пишешь, не приходя в сознание, за секунды. (Впрочем, я запускал расчёты на оч. слабеньком лаптопе.)

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение06.05.2017, 14:41 
Заслуженный участник


10/01/16
2318
Среднее геометрическое нетривиального подмножесва из чисел, не больших $n$, также не больше $n$. Если оно не входит в подмножество, добавим его к подмножеству - и получим новое "путнинское" (а если входит - удалим). (В двухэлементное - не входит). Поэтому все нетривиальные путные подмножества разбиваются на пары. Поэтому их кол-во - четно.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение06.05.2017, 16:06 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Что ж, вот, наконец, и доказательство :appl: Впрочем, структура последовательности по-прежнему малость загадочна.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение06.05.2017, 22:43 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
Да, я искал, что можно было бы выкинуть из семейства, но не нашел:) :appl:
Aritaborian, на 2.4ггц Xeon до 50 ухожит примерно 40 секунд. Тут важнее не платформа, а алгоритм (я перебираю гораздо меньше, чем все подмножества). Mathematica, думаю, с тем же алгоритмом будет медленнее раз в 5.

 Профиль  
                  
 
 Re: Подмножества с целым средним геометрическим
Сообщение06.05.2017, 22:54 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Теоретически можно переписать ваш алгоритм на Wolfram Language (приведённый же мною перебирает тупо всё в лоб) и даже попросить Математику скомпилировать... Если скомпилирует, по времени будет сравнимо. А так, да, что касается скорости, Математика супротив Си всегда была как плотник супротив столяра, кто ж спорит.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group