Sprawdzenie podzielności 1749060 liczb zadanych wzorem

matemix · Post autor: **matemix** » 12 mar 2016, o 02:15

Czy wśród liczb postaci:

\(\displaystyle{ \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]}\)

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

Istnieje liczba podzielna przez:

\(\displaystyle{ 2^{78}-49667^{5}=13734584404743437}\)

Można znaleźć \(\displaystyle{ 1749060}\) różnych liczb powyższej postaci. Nie jest to skomplikowane zadanie dla komputera, ale nie mam programu, który by mi to sprawdził.

SlotaWoj · Post autor: **SlotaWoj** » 12 mar 2016, o 03:18

Ale to nie są liczby postaci, ale wektory!

matemix · Post autor: **matemix** » 12 mar 2016, o 14:21

SlotaWoj pisze: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:

\(\displaystyle{ x_{1}=2, x_{2}=2, x_{3}=2, x_{4}=2}\)

\(\displaystyle{ (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:

\(\displaystyle{ 2^{78}-49667^{5}=13734584404743437}\)

Premislav · Post autor: **Premislav** » 12 mar 2016, o 17:25

Policzyłem to na kartce A5 i odpowiedź brzmi "nie".
Wybaczcie, nie mogłem się powstrzymać.

matemix · Post autor: **matemix** » 12 mar 2016, o 17:30

Premislav pisze:Policzyłem to na kartce A5 i odpowiedź brzmi "nie".
Wybaczcie, nie mogłem się powstrzymać.

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 \(\displaystyle{ 5}\) oraz \(\displaystyle{ 181}\). Jeżeli rozwiązania wystąpią \(\displaystyle{ 49667}\) jest liczbą Crandalla.

Medea 2 · Post autor: **Medea 2** » 12 mar 2016, o 21:22

Brutalnym rozwiązaniem mathematicznym jest

Kod: Zaznacz cały

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]

matemix · Post autor: **matemix** » 12 mar 2016, o 22:23

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.

matemix · Post autor: **matemix** » 22 mar 2016, o 23:16

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: Zaznacz cały

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

matemix · Post autor: **matemix** » 19 kwie 2016, o 21:35

Dodam tylko, że po zainstalowaniu biblioteki GMP sprawdziłem te wszystkie liczby. Żadne rozwiązanie nie jest liczbą naturalną.

SlotaWoj · Post autor: **SlotaWoj** » 19 kwie 2016, o 21:52

Potrzebne jest inne narzędzie programistyczne lub trzeba w C++ zrobić funkcje np. do 128-bitowej (16 bajtów) arytmetyki całkowitej.

matemix · Post autor: **matemix** » 20 kwie 2016, o 08:36

SlotaWoj pisze: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.

Medea 2 · Post autor: **Medea 2** » 20 kwie 2016, o 08:49

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: Zaznacz cały

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ę \(\displaystyle{ \{x_1, x_2, x_3, x_,4\}}\) i liczy... wiadomo, co liczy Szesnastokrotny iloczyn skalarny wektora \(\displaystyle{ \{0, 1, 2, 3, 4\}}\), na który nałożono funkcję \(\displaystyle{ n \mapsto (49667 / 2)^n}\) oraz \(\displaystyle{ \{x_1, x_2, x_3, x_4, 0\}}\), który oberwał funkcją \(\displaystyle{ n \mapsto 2^n}\).

W drugiej ze zbioru \(\displaystyle{ \{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 \(\displaystyle{ 2^{78} - 49667^5}\) jest zerem. Rzeczywiście, nie ma żadnego.

matemix · Post autor: **matemix** » 20 kwie 2016, o 16:59

Medea 2 pisze: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 \(\displaystyle{ p}\) dla, których występują rozwiązania całkowite:

\(\displaystyle{ 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}}}\)

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

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

\(\displaystyle{ {y+x \choose y} \cdot \frac {y} {x+y}}\)

Szacuję, że program może liczyć miesiące, a nawet lata dla \(\displaystyle{ y}\) większych niż \(\displaystyle{ 10}\). Z kolei dla mniejszych wartości \(\displaystyle{ 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 \(\displaystyle{ {2^{x+y}-p^{y}}\) (względem licznika, który przyjmuje wartości od \(\displaystyle{ p^y-2^y}\) do około \(\displaystyle{ (p^y-2^y) \cdot 2^x}\)), zatem dobierałem \(\displaystyle{ p}\) będące podłogą pierwiastków y-stopnia z kolejnych potęg liczby \(\displaystyle{ {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 \(\displaystyle{ p=3}\), \(\displaystyle{ p=5}\) i \(\displaystyle{ p=181}\).

Medea 2 pisze: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: Zaznacz cały
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ę \(\displaystyle{ \{x_1, x_2, x_3, x_,4\}}\) i liczy... wiadomo, co liczy Szesnastokrotny iloczyn skalarny wektora \(\displaystyle{ \{0, 1, 2, 3, 4\}}\), na który nałożono funkcję \(\displaystyle{ n \mapsto (49667 / 2)^n}\) oraz \(\displaystyle{ \{x_1, x_2, x_3, x_4, 0\}}\), który oberwał funkcją \(\displaystyle{ n \mapsto 2^n}\).

W drugiej ze zbioru \(\displaystyle{ \{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 \(\displaystyle{ 2^{78} - 49667^5}\) jest zerem. Rzeczywiście, nie ma żadnego.

W czym jest napisany ten kod?