szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 mar 2016, o 02:15 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Czy wśród liczb postaci:

\left( 1, \frac {49667} {2}, \frac {49667^{2}} {4},  \frac{ 49667^{3}} {8}, \frac {49667^{4}} {16} \right)  \cdot 16 \cdot \left[\begin{array}{ccc}2^{x_{1}}\\2^{x_{2}}\\2^{x_{3}}\\2^{x_{4}}\\1\end{array}\right]

x_{1}, x_{2}, x_{3}, x_{4} \in  \left[ 0,78 \right]
x_{1} \ge x_{2} \ge x_{3} \ge x_{4}

Istnieje liczba podzielna przez:

2^{78}-49667^{5}=13734584404743437

Można znaleźć 1749060 różnych liczb powyższej postaci. Nie jest to skomplikowane zadanie dla komputera, ale nie mam programu, który by mi to sprawdził.
Góra
Mężczyzna Online
PostNapisane: 12 mar 2016, o 03:18 
Moderator

Posty: 3787
Lokalizacja: Kraków PL
Ale to nie są liczby postaci, ale wektory!
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2016, o 14:21 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
SlotaWoj napisał(a):
Ale to nie są liczby postaci, ale wektory!


Poprawiłem. Z rozpędu w pierwszym wektorze napisałem znaki "+" zamiast przecinków.

Dla pewności zapiszę przykład. Niech:

x_{1}=2, x_{2}=2, x_{3}=2, x_{4}=2

(1, \frac {49667} {2}, \frac {49667^{2}} {4},  \frac{ 49667^{3}} {8}, \frac {49667^{4}} {16}) \cdot 16 \cdot \left[\begin{array}{ccc}2^{2}\\2^{2}\\2^{2}\\2^{2}\\1\end{array}\right]=4+4 \cdot \frac {49667} {2}+4 \cdot \frac {49667^{2}} {4}+4 \cdot \frac {49667^{3}} {8}+ \frac {49667^{4}} {16}) \cdot 16=
6086136154330925657

Nie dzieli się przez:

2^{78}-49667^{5}=13734584404743437
Góra
Mężczyzna Online
PostNapisane: 12 mar 2016, o 17:25 
Użytkownik
Avatar użytkownika

Posty: 10579
Lokalizacja: Wrocław
Policzyłem to na kartce A5 i odpowiedź brzmi "nie".
Wybaczcie, nie mogłem się powstrzymać. :D
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2016, o 17:30 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Premislav napisał(a):
Policzyłem to na kartce A5 i odpowiedź brzmi "nie".
Wybaczcie, nie mogłem się powstrzymać. :D


Rozumiem, że nie sprawdzałeś wszystkich przypadków. Jak udało Ci się je ograniczyć?

Dodam może jeszcze, że problem ma związek z poszukiwaniem liczb Crandalla nie będących liczbami Wieferich. Znane są tylko dwie takie liczby 5 oraz 181. Jeżeli rozwiązania wystąpią 49667 jest liczbą Crandalla.
Góra
Kobieta Offline
PostNapisane: 12 mar 2016, o 21:22 
Użytkownik
Avatar użytkownika

Posty: 2505
Brutalnym rozwiązaniem mathematicznym jest

Kod:
1
2
3
4
5
k = 2^78 - 49667^5;
l = 49667/2;
fun[lis_] :=
 Mod[Total[(l^{0, 1, 2, 3, 4})*16*2^Flatten[{lis, 0}]], k] == 0
Select[Select[Tuples[Range[0, 78], 4], Reverse[Sort[#]] == # &], fun]
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2016, o 22:23 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Podejrzewałem, że kod programu może być krótki. Niestety nie potrafię przełożyć go na język C, którego podstawy znam, ani nie wiem w jakim języku został napisany powyższy kod.
Góra
Mężczyzna Offline
PostNapisane: 22 mar 2016, o 23:16 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Mam kod programu, który to policzy. Niestety program znajduje nieprawdziwe wyniki. Prawdopodobnie błędnie wykonuje dziele dużych liczb, bo są one za duże.

Kod:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <iomanip>
using namespace std;
#include <conio.h>
#include <string>
#include <vector>
#include <cmath>
#include <limits>

//====================================================================================================================

double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs );
bool isNaturalNum( double value );
double newton( unsigned int n, unsigned int k );

//====================================================================================================================

int main()
{
    int x = 73;
    int y = 5;
    int p = 49667;
   
    cout << "Podaj p: ";
    cin >> p;
    cout << "Podaj y: ";
    cin >> y;
    cout << "Podaj x: ";
    cin >> x;
   
    vector < vector < int >> xn( y - 1, vector < int >( x + 1 ) );
   
    for( auto & vec: xn )
    {
        for( int i = 0; i <= x; ++i )
        {
            vec[ i ] = i;
        }
    }
   
    vector < int > xIndxs( xn.size(), 0 );
    double w;
    bool exit = false;
    double counter = 0;
    unsigned long long howManyFound = 0;
   
    cout << "Start " << endl;
   
    while( !exit )
    {
        counter++;
       
        w = computeW( x, y, p, xn, xIndxs );
        if( isNaturalNum( w ) )
        {
            ++howManyFound;
           
            cout << "w= " << fixed << w << "; ";
            for( int i = 0; i < xn.size(); ++i )
            {
                cout << "x" << i + 1 << "=" << xn[ i ][ xIndxs[ i ] ] <<( i == xn.size() - 1 ? ""
                    : ", " );
            }
            cout << endl;
        }
       
        ++xIndxs[ 0 ];
       
        for( int j = xIndxs.size() - 1; j > 0; --j )
        {
            if( xIndxs[ j ] == x )
            {
                if( j == xIndxs.size() - 1 ) { exit = true; break; }
               
                ++xIndxs[ j + 1 ];
               
                for( int pom = j; pom >= 0; --pom )
                {
                    xIndxs[ pom ] = xIndxs[ j + 1 ];
                }
               
                break;
            }
        }
       
        if( xIndxs[ 0 ] == x + 1 )
        {
            if( xIndxs.size() >= 2 )
            {
                ++xIndxs[ 1 ];
                xIndxs[ 0 ] = xIndxs[ 1 ];
            }
            else
            {
                exit = true;
            }
        }
    }
   
    cout << "Koniec" << endl;
    cout << "wszystkich iteracji: " << fixed << setprecision( 0 ) << counter << endl;
    cout << "Policzonych, calkowitych liczb w: " << howManyFound << endl;
   
    getch();
    return 0;
}
//====================================================================================================================
double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs )
{
    double retVal = 0;
   
    int lastPow;
    for( int i = 0; i < pXn.size(); ++i )
    {
        retVal += pow( 2, pXn[ i ][ pXIndxs[ i ] ] ) * pow( pP, i ) / pow( 2, i );
       
        lastPow = i + 1;
    }
   
    retVal += pow( pP, pY - 1 ) / pow( 2, pY - 1 );
    retVal *= pow( 2, pY - 1 );
    retVal /= pow( 2, pX + pY ) - pow( pP, pY );
   
    return retVal;
}

//*****************************************************************************
bool isNaturalNum( double value )
{
    unsigned long long intPart = value;
    double rest = value - intPart;
   
    return rest == 0;
}
//*****************************************************************************
double newton( unsigned int n, unsigned int k ) // not working
{
    double Wynik = 1;
   
    for( unsigned int i = 1; i <= k; i++ )
    {
        Wynik = Wynik *( n - i + 1 ) / i; // Obliczanie ze wzoru iteracyjnego
    }
   
    return Wynik;
}
Góra
Mężczyzna Offline
PostNapisane: 19 kwi 2016, o 20:35 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Dodam tylko, że po zainstalowaniu biblioteki GMP sprawdziłem te wszystkie liczby. Żadne rozwiązanie nie jest liczbą naturalną.
Góra
Mężczyzna Online
PostNapisane: 19 kwi 2016, o 20:52 
Moderator

Posty: 3787
Lokalizacja: Kraków PL
Potrzebne jest inne narzędzie programistyczne lub trzeba w C++ zrobić funkcje np. do 128-bitowej (16 bajtów) arytmetyki całkowitej.
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2016, o 07:36 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
SlotaWoj napisał(a):
Potrzebne jest inne narzędzie programistyczne lub trzeba w C++ zrobić funkcje np. do 128-bitowej (16 bajtów) arytmetyki całkowitej.


Właśnie napisałem, że dzięki bibliotece GMP, która oferuje duże (nieograniczone) zmienne policzyłem wszystkie rozwiązania, więc problem rozwiązany.
Góra
Kobieta Offline
PostNapisane: 20 kwi 2016, o 07:49 
Użytkownik
Avatar użytkownika

Posty: 2505
Jeżeli cenisz sobie swój czas i kompletnie nie zależy Ci na tym, jak szybko wykonuje się program, ale nie masz nic przeciwko szybszemu pisaniu kodu, to naprawdę polecam jakiś pakiet matematyczny, a nie C++.

Swoją drogą mój poprzedni kod za nic w świecie nie ma prawa działać, więc proszę mnie nie bić, nie krzyczeć i przyjąć pomyłkę ze spokojem. Nowy, tym razem sprawdzony to

Kod:
1
2
3
fun[lista_] := 16*((49667/2)^{0, 1, 2, 3, 4}).(2^Flatten[{lista, 0}])
listy = Map[Reverse, Subsets[Range[0, 78], {4}]];
Select[listy, Mod[fun[#], ] == 0 &]


W pierwszej linijce definiuję funkcję, która przyjmuje listę \{x_1, x_2, x_3, x_,4\} i liczy... wiadomo, co liczy :D Szesnastokrotny iloczyn skalarny wektora \{0, 1, 2, 3, 4\}, na który nałożono funkcję n \mapsto (49667 / 2)^n oraz \{x_1, x_2, x_3, x_4, 0\}, który oberwał funkcją n \mapsto 2^n.

W drugiej ze zbioru \{0, 1, \ldots, 77, 78\} wybieram czteroelementowe podzbiory (właściwie: podlisty) i sortuję malejąco.

W trzeciej ze wszystkich wybieram te, dla których funkcja z pierwszej linijki modulo 2^{78} - 49667^5 jest zerem. Rzeczywiście, nie ma żadnego.
Góra
Mężczyzna Offline
PostNapisane: 20 kwi 2016, o 15:59 
Użytkownik

Posty: 364
Lokalizacja: Wrocław
Medea 2 napisał(a):
Jeżeli cenisz sobie swój czas i kompletnie nie zależy Ci na tym, jak szybko wykonuje się program, ale nie masz nic przeciwko szybszemu pisaniu kodu, to naprawdę polecam jakiś pakiet matematyczny, a nie C++.


W przypadku większości problemów czas wykonywania się programu nie ma większego znaczenia. Jaki pakiet matematyczny polecasz?

Natomiast w przypadku tego programu czas jego wykonywania się ma ogromne znaczenie. Ogólnie znalezienie jakichkolwiek p dla, których występują rozwiązania całkowite:

w = \left( 1, \frac {p^{1}} {2}, \frac {p^{2}} {4},  \frac{ p^{3}} {8}, ... ,  \frac {p^{y-1}} {2^{y-1}} \right)  \cdot 2^{y-1} \cdot \left[\begin{array}{ccc}2^{x_{1}}\\2^{x_{2}}\\2^{x_{3}}\\.\\.\\.\\2^{x_{y-1}}\\1\end{array}\right] \cdot \frac {1} {2^{x+y}-p^{y}}

x_{1}, x_{2}, x_{3}, ..., x_{y-1} \in  \left[ 0,x \right]
x_{1} \ge x_{2} \ge x_{3} \ge ... \ge x_{y-1}

dla naturalnych p, y i x jest bardzo trudnym zadaniem. Wszystko przez to, że ilość rozwiązań jest dana wzorem:

{y+x \choose y} \cdot \frac {y} {x+y}

Szacuję, że program może liczyć miesiące, a nawet lata dla y większych niż 10. Z kolei dla mniejszych wartości y ciekawych "rokujących" rozwiązań do sprawdzenia jest raczej niewiele. Ale może źle dobierałem zmienne. Starałem się uzyskać jak najmniejszy mianownik {2^{x+y}-p^{y} (względem licznika, który przyjmuje wartości od p^y-2^y do około (p^y-2^y) \cdot 2^x), zatem dobierałem p będące podłogą pierwiastków y-stopnia z kolejnych potęg liczby {2^{x+y}. Prawdopodobieństwo może wskazywać, że im mniejszy będzie ten mianownik względem licznika tym większe szanse, że zajdzie podzielność. Ogólnie problem jest otwarty, a jedyne rozwiązania są znane dla p=3, p=5 i p=181.


Medea 2 napisał(a):
Swoją drogą mój poprzedni kod za nic w świecie nie ma prawa działać, więc proszę mnie nie bić, nie krzyczeć i przyjąć pomyłkę ze spokojem. Nowy, tym razem sprawdzony to

Kod:
1
2
3
fun[lista_] := 16*((49667/2)^{0, 1, 2, 3, 4}).(2^Flatten[{lista, 0}])
listy = Map[Reverse, Subsets[Range[0, 78], {4}]];
Select[listy, Mod[fun[#], ] == 0 &]


W pierwszej linijce definiuję funkcję, która przyjmuje listę \{x_1, x_2, x_3, x_,4\} i liczy... wiadomo, co liczy :D Szesnastokrotny iloczyn skalarny wektora \{0, 1, 2, 3, 4\}, na który nałożono funkcję n \mapsto (49667 / 2)^n oraz \{x_1, x_2, x_3, x_4, 0\}, który oberwał funkcją n \mapsto 2^n.

W drugiej ze zbioru \{0, 1, \ldots, 77, 78\} wybieram czteroelementowe podzbiory (właściwie: podlisty) i sortuję malejąco.

W trzeciej ze wszystkich wybieram te, dla których funkcja z pierwszej linijki modulo 2^{78} - 49667^5 jest zerem. Rzeczywiście, nie ma żadnego.


W czym jest napisany ten kod?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 (4 zadania) Sprawdz podzielność liczb przez 10  Anonymous  4
 Czy podana liczba jest różnicą kwadratów 2 liczb calko  pennywise  1
 Dowód na poprawność zasady podzielności przez 9  magik100  12
 Udowodnij cechy podzielności przez 7 i 8  Anonymous  6
 Różnica cyfr pewnej liczby wynosi 5 ... Znajdź tę liczb  Tomasz B  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl