indexieren:

volkard

brak schrieb:

die 39 als Spiegelzahl hat mindestens 3 ketten, davon ist die mit Zahl 26 trivial

hier die Ketten für Zahl 21 und 22

21 3 33 27 15 9 21 3 33 27 15 9 21 3 33 27 15 9 21 3 33 27 15 9 21

22 5 29 19 1 37 35 31 23 7 25 11 17 5 29 19 1 37 35 31 23 7 25 11 17

Beachte die Kettenlängen:
21 3 33 27 15 9 21 3 33 27 15 9 21 (3 33 27 15 9 21 3 33 27 15 9 21)

22 5 29 19 1 37 35 31 23 7 25 11 17 (5 29 19 1 37 35 31 23 7 25 11 17)

gleich. Jede Spiegelzahl kann nur eine kleine Anzahl von Kettenlängen produzieren. Hier 12, und ich halte es für keinen Zufall, daß das nur eins weniger ist als der große Teiler 13 in der 39.
Gibts ähnliche Auffälligkeiten bei Spiegelzahlen wie 51=3*17 oder 57=3*19?

Zum Zyklenfinden bietet sich http://en.wikipedia.org/wiki/Cycle_detection an, da brauchste keine map mehr. (Nicht auf die deutsche Version dieses Artikel klicken, der ist beschämend schlecht.)

Ich hab mal Leezeichen dazwischengesetzt:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

string int_to_string( int zahl )
{
    ostringstream oss;
    oss << zahl;
    return oss.str();
}

struct kette
{
    int zahl;
    int faktor;
    int spiegelzahl;
    string k;
};

kette mach_kette( int zahl, int faktor, int spiegelzahl )
{
    kette k = { zahl, faktor, spiegelzahl, ">" + int_to_string(zahl) + "< " };
	vector<int> glieder;

	for(map<int,unsigned> vorkommen;;)
    {
        zahl *= faktor;
        zahl  = abs( spiegelzahl-zahl );

		glieder.push_back( zahl );

		if( glieder.size()%2==0 && equal( glieder.begin(),glieder.begin()+(glieder.size()/2), glieder.begin()+(glieder.size()/2)) )
		{
			for(unsigned i=0; i!=glieder.size()/2; ++i)
				k.k += int_to_string( glieder[i] ) + " ";

			return k;
		}
    }
}

int main()
{
    map< string,vector<kette> > zahlenspiel;
    for(int zahl=20; zahl!=25; ++zahl)
    {
		for(int spiegelzahl=39; spiegelzahl!=40; ++spiegelzahl)
		{
			kette k = mach_kette( zahl, 2, spiegelzahl );
			zahlenspiel[k.k].push_back( k );
		}
    }

    for(map< string,vector<kette> >::iterator it=zahlenspiel.begin(); it!=zahlenspiel.end(); ++it)
    {
        vector<kette>& vec = it->second;
        for(vector<kette>::iterator itk=vec.begin(); itk!=vec.end(); ++itk)
        {
            cout << "Kette = " << itk->k  << '\n';
        }
        cout << '\n';
    }
}

Die for-Schleife für den Faktor hab ich rausgenommen und auf 2 gesetzt, damit es terminiert, wie volkard gesagt hat.

Bei deinem Beispiel hast du bei 21 ja ein Fehler drin, oder?:D Das wiederholt sich doch vorher schon.

brak

Verdoppelung der Spiegelzahl bringt keine längere Kette, sondern die Verdoppelung der Werte der Kette .... ist irgendwie logisch

Jede Spiegelzahl kann nur eine kleine Anzahl von Kettenlängen produzieren.

Woher weißt Du das? Hast Du schon mal Spiegelzahl 199458 durchgerattert?

volkard

brak schrieb:

Verdoppelung der Spiegelzahl bringt keine längere Kette, sondern die Verdoppelung der Werte der Kette .... ist irgendwie logisch

Jede Spiegelzahl kann nur eine kleine Anzahl von Kettenlängen produzieren.

Woher weißt Du das? Hast Du schon mal Spiegelzahl 199458 durchgerattert?

Nur 7 Zykluslängen.

Bitte Spiegelzahl eingeben: 199458
laenge	anzahl
1	5
3	24
6	96
791	3164
1582	6328
2373	18984
4746	170856

199458=2*3*3*7*1583
Zykluslänge 1582 taucht wiedermal auf.

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

int64_t f(int64_t zahl,int64_t spiegelzahl){
	return abs(spiegelzahl-2*zahl);
}

int64_t findeZyklus(int64_t zahl,int64_t spiegelzahl){
	int64_t igel=zahl;
	int64_t hase=zahl;
	do{
		igel=f(igel,spiegelzahl);
		hase=f(hase,spiegelzahl);
		hase=f(hase,spiegelzahl);
	}while(hase!=igel);
	return hase;
}

int64_t findeZyklusLaenge(int64_t zahl,int64_t spiegelzahl){
	int64_t igel=findeZyklus(zahl,spiegelzahl);
	int64_t hase=igel;
	int64_t len=0;
	do{
		hase=f(hase,spiegelzahl);
		++len;
	}while(hase!=igel);
	return len;
}

int main()
{
	cout<<"Bitte Spiegelzahl eingeben: ";
	int64_t spiegelzahl;
	cin>>spiegelzahl;

	map<int64_t,int64_t> zyklenLaengen;

	for(int64_t startzahl=1;startzahl<spiegelzahl;++startzahl)
		++zyklenLaengen[findeZyklusLaenge(startzahl,spiegelzahl)];

	cout<<"laenge\tanzahl\n";
	for(auto i:zyklenLaengen)
		cout<<i.first<<"\t"<<i.second<<'\n';
}

Schau Die mal die Spiegelzahlen zwischen 65530 und 65540 an.

brak

Ich möchte mal fragen, warum das Teil von out so langsam arbeitet. Was ist denn der spez. Befehl der soviel Zeit kostet. Ich lade gerade Zahl 1 - 50, spiegelzahl hundert durchlaufen, der Computer arbeitet wie wild, wird aber irgendwie nicht fertig .... ich meine, es sind ein paar Additionen und Subtraktionen, wie haben 2014 und der Computer ist kein C64 mehr -... wunder, wunder ...

volkard

brak schrieb:

Ich möchte mal fragen, warum das Teil von out so langsam arbeitet. Was ist denn der spez. Befehl der soviel Zeit kostet. Ich lade gerade Zahl 1 - 50, spiegelzahl hundert durchlaufen, der Computer arbeitet wie wild, wird aber irgendwie nicht fertig .... ich meine, es sind ein paar Additionen und Subtraktionen, wie haben 2014 und der Computer ist kein C64 mehr -... wunder, wunder ...

Weil er algorithmisch getrixt hat.
In Zeile 37 ist der Hase elendlich verendet.
Hab keine Ahnung, was die machen soll. Aber um nen Zykus aufzudecken, reicht bereits eine einzige Wiederholung, es müssen nicht deren drei sein oder die Hälfte aller Zahlen.
16G Ram reichen schonmal nicht aus. Ich fürchte, mit noch mehr braucht man es nicht zu probieren.

brak

volkard schrieb:

Weil er algorithmisch getrixt hat.
In Zeile 37 ist der Hase verendet.

kann man das nicht untrixy machen? Ich bin, wie schon bemerkt, kein Programmierungsprofi, aber irgendwie habe ich eine andere Vorstellung von Performance ...:-)

volkard

brak schrieb:

volkard schrieb:

Weil er algorithmisch getrixt hat.
In Zeile 37 ist der Hase verendet.

kann man das nicht untrixy machen? Ich bin, wie schon bemerkt, kein Programmierungsprofi, aber irgendwie habe ich eine andere Vorstellung von Performance ...:-)

Einmal den dunklen Weg beschritten, muss man dabeibleiben, fürchte ich.
So klapp's wieder:

if( glieder.size()%2==0 && equal( glieder.begin()+(glieder.size()/3),glieder.begin()+(glieder.size()*2/3), glieder.begin()+(glieder.size()*2/3)) )

brak

volkard schrieb:

Einmal den dunklen Weg beschritten, muss man dabeibleiben, fürchte ich.

Was meinst Du denn pragrammiertechnisch mit "Dunkler Weg", den out beschritten habe? Der Austausch von 1/2 durch 2/3 kann es ja auch nicht sein ....

volkard

brak schrieb:

volkard schrieb:

Einmal den dunklen Weg beschritten, muss man dabeibleiben, fürchte ich.

Was meinst Du denn pragrammiertechnisch mit "Dunkler Weg", den out beschritten habe? Der Austausch von 1/2 durch 2/3 kann es ja auch nicht sein ....

Doch, 2/3 ist viel freundlicher als 1/2.

Er merkt sich die bisherigen Zahlen.
Und vergleicht die erste Hälfte mit der Zweiten Hälfte.
Aber bei Folgen wie
22 5 29 19 1 37 35 31 23 7 25 11 17 (5 29 19 1 37 35 31 23 7 25 11 17)
hat er einfach Pech, die Startzahl kommt nicht im Zyklus vor!
Es können am Anfang auch mehrere Zahlen sein, die nicht im Zyklus sind, man kann vorher nicht wissen, wie viele.
Deswegen muss beim Vergleichen am Anfang genug weggelassen werden.
Ich vergleiche deswegen nicht die erste Hälfte mit der zweiten Hälfte, sondern das zweite Drittel mit dem dritten Drittel.

volkard

Kleine Liste mit Rekord-Zykluslängenanzahlen:
3 1
9 2
15 3
45 5
105 6
135 7
225 8
405 9
675 11
1485 13
2025 14
3375 15
4455 17
9315 18
Bis 10000 maximal 18 Zykluslängen. Und die Rekord-Spiegelzahlen haben sehr ähnliche Primfaktorzerlegungen: viel 3, fast so viel 5, und selten mal was anderes.

brak

volkard schrieb:

Kleine Liste mit Rekord-Zykluslängenanzahlen:
3 1
.
.
4455 17
9315 18
Bis 10000 maximal 18 Zykluslängen. Und die Rekord-Spiegelzahlen haben sehr ähnliche Primfaktorzerlegungen: viel 3, fast so viel 5, und selten mal was anderes.

kann nicht stimmen, Volkhard

schon 58 Spiegelzahl hat eine Zykluslänge von 14 (50 42 26 6 46 34 10 38 18 22 14 30 2)
Bei Faktor 2 und Zahl 8.

Ich arbeite mit Excel, und wollte das automatisieren mit C++ um an große Zahlen ranzukommen. So habe ich gute Kontrolle

brak

volkard schrieb:

Es können am Anfang auch mehrere Zahlen sein, die nicht im Zyklus sind, man kann vorher nicht wissen, wie viele.
Deswegen muss beim Vergleichen am Anfang genug weggelassen werden.
Ich vergleiche deswegen nicht die erste Hälfte mit der zweiten Hälfte, sondern das zweite Drittel mit dem dritten Drittel.

Deswegen hatte ich die Idee, die Zahlen zu indizieren, denn eine Zahl kann erst ein zweites mal vorkommen, wenn der Zyklus schon einmal durch ist. Er braucht doch gar nicht den ganzen Schwanz bis zur halben Spiegelzahl zu rechnen ....

volkard schrieb:

Er merkt sich die bisherigen Zahlen.
Und vergleicht die erste Hälfte mit der Zweiten Hälfte.
Aber bei Folgen wie
22 5 29 19 1 37 35 31 23 7 25 11 17 (5 29 19 1 37 35 31 23 7 25 11 17)
hat er einfach Pech, die Startzahl kommt nicht im Zyklus vor!

ich denke, das ist zu umständlich ...

wahr ist auch: Je größer die Spiegelzahl, desto mehr Zahlen bis zum Beginn des Zyklus...

volkard

brak schrieb:

volkard schrieb:

Kleine Liste mit Rekord-Zykluslängenanzahlen:
3 1
.
.
4455 17
9315 18
Bis 10000 maximal 18 Zykluslängen. Und die Rekord-Spiegelzahlen haben sehr ähnliche Primfaktorzerlegungen: viel 3, fast so viel 5, und selten mal was anderes.

kann nicht stimmen, Volkhard

schon 58 Spiegelzahl hat eine Zykluslänge von 14 (50 42 26 6 46 34 10 38 18 22 14 30 2)
Bei Faktor 2 und Zahl 8.

Ich arbeite mit Excel, und wollte das automatisieren mit C++ um an große Zahlen ranzukommen. So habe ich gute Kontrolle

Ja, bei Spiegelzahl 58 gibt es eine Startzahl, die einen Zyklus mit Länge 1 produziert und 56 Startzahlen, die einen Zyklus mit Länge 14 produzieren.
Also zwei verschiedene Zykluslängen.
Das ist die Ausgabe meines ersten Hase-Igel-Programms.
Die 9315 hat 18 verschiedene Zykluslängen.

brak

volkard schrieb:

Die 9315 hat 18 verschiedene Zykluslängen.

kann ich jetzt grob bestätigen, weil bei mir ungerade Spiegelzahlen nur diverse Mixturen der ungeraden Zahlen unter ihr als Zyklus anbieten.

Faktor 2 Spiegelzahl 31 (Symmetrie gut zu erkennen!)

Beginn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23
2 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15
3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7
4 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1
5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9
6 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17
7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25
8 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29
9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21
10 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13
11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5
12 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3
13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11
14 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19
15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27
16 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27
17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19
18 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11
19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3
20 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5
21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13
22 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21
23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29
24 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25
25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7 17
26 21 11 9 13 5 21 11 9 13 5 21 11 9 13 5 21 11 9
27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1
28 25 19 7 17 3 25 19 7 17 3 25 19 7 17 3 25 19 7
29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23 15
30 29 27 23 15 1 29 27 23 15 1 29 27 23 15 1 29 27 23
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31

sag bitte nochmal was zur Schwerfälligkeit des Programm, oder post ein besseres, nicht so arschlangsames, ich will forschen ....

volkard schrieb:

brak schrieb:

Ich möchte mal fragen, warum das Teil von out so langsam arbeitet. Was ist denn der spez. Befehl der soviel Zeit kostet. Ich lade gerade Zahl 1 - 50, spiegelzahl hundert durchlaufen, der Computer arbeitet wie wild, wird aber irgendwie nicht fertig .... ich meine, es sind ein paar Additionen und Subtraktionen, wie haben 2014 und der Computer ist kein C64 mehr -... wunder, wunder ...

Weil er algorithmisch getrixt hat.

Im Algorithmen finden bin ich nicht sehr begabt.

volkard schrieb:

Schau Die mal die Spiegelzahlen zwischen 65530 und 65540 an.

#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;

long long mul_abstand( long long zahl, long long spiegelzahl )
{
	const int faktor = 2;
    return abs( spiegelzahl - faktor*zahl );
}

long long finde_zyklus( long long zahl, long long spiegelzahl )
{
    long long glied_x = zahl;
    long long glied_y = zahl;
    do
	{
        glied_x = mul_abstand( glied_x, spiegelzahl );
        glied_y = mul_abstand( glied_y, spiegelzahl );
        glied_y = mul_abstand( glied_y, spiegelzahl );
    }
	while( glied_x != glied_y );

    return glied_y;
}

long long finde_zyklus_laenge( long long zahl, long long spiegelzahl )
{
    long long glied_y = finde_zyklus( zahl, spiegelzahl );
    long long glied_x = glied_y;
    long long len  = 0;
    do
	{
        glied_x = mul_abstand( glied_x, spiegelzahl );
        ++len;
    }
	while( glied_x != glied_y );

    return len;
}

int main()
{
	map<long long,map<long long,long long>> zyklen_laengen;

	long long begin_startzahl   = 1;
	long long begin_spiegelzahl = 65530;

	long long end_startzahl     = begin_spiegelzahl; // end = ausschliesslich
	long long end_spiegelzahl   = 65541;

	for(long long startzahl=begin_startzahl; startzahl!=end_startzahl; ++startzahl)
	{
		for(long long spiegelzahl=begin_spiegelzahl; spiegelzahl!=end_spiegelzahl; ++spiegelzahl)
		{
			++zyklen_laengen[ spiegelzahl ][ finde_zyklus_laenge(startzahl,spiegelzahl) ];
		}
	}

	for(const auto& p : zyklen_laengen)
	{
		cout << "Alle Zykluslaengen der Spiegelzahl " << p.first << ':' << '\n';

		for(const auto& m : p.second)
		{
			cout << "Zykluslaenge " << m.first << " kommt " << m.second << "x vor" << '\n';
		}
		cout << '\n';
	}
}

Misst die Ausgabe vergessen:

Alle Zykluslaengen der Spiegelzahl 65530:
Zykluslaenge 1 kommt 1x vor
Zykluslaenge 2 kommt 8x vor
Zykluslaenge 117 kommt 13104x vor
Zykluslaenge 468 kommt 52416x vor

Alle Zykluslaengen der Spiegelzahl 65531:
Zykluslaenge 9 kommt 18x vor
Zykluslaenge 431 kommt 3448x vor
Zykluslaenge 7758 kommt 62063x vor

Alle Zykluslaengen der Spiegelzahl 65532:
Zykluslaenge 1 kommt 11x vor
Zykluslaenge 7 kommt 1008x vor
Zykluslaenge 14 kommt 64510x vor

Alle Zykluslaengen der Spiegelzahl 65533:
Zykluslaenge 6 kommt 12x vor
Zykluslaenge 35 kommt 70x vor
Zykluslaenge 420 kommt 840x vor
Zykluslaenge 2485 kommt 4970x vor
Zykluslaenge 29820 kommt 59637x vor

Alle Zykluslaengen der Spiegelzahl 65534:
Zykluslaenge 1 kommt 1x vor
Zykluslaenge 3 kommt 12x vor
Zykluslaenge 5 kommt 60x vor
Zykluslaenge 15 kommt 65456x vor

Alle Zykluslaengen der Spiegelzahl 65535:
Zykluslaenge 1 kommt 2x vor
Zykluslaenge 2 kommt 4x vor
Zykluslaenge 4 kommt 24x vor
Zykluslaenge 8 kommt 480x vor
Zykluslaenge 16 kommt 65019x vor

Alle Zykluslaengen der Spiegelzahl 65536:
Zykluslaenge 1 kommt 65529x vor

Alle Zykluslaengen der Spiegelzahl 65537:
Zykluslaenge 16 kommt 65529x vor

Alle Zykluslaengen der Spiegelzahl 65538:
Zykluslaenge 1 kommt 5x vor
Zykluslaenge 3 kommt 12x vor
Zykluslaenge 5 kommt 60x vor
Zykluslaenge 15 kommt 65452x vor

Alle Zykluslaengen der Spiegelzahl 65539:
Zykluslaenge 32769 kommt 65529x vor

Alle Zykluslaengen der Spiegelzahl 65540:
Zykluslaenge 1 kommt 3x vor
Zykluslaenge 2 kommt 16x vor
Zykluslaenge 14 kommt 65510x vor

Zykluslaenge 29820 kommt 59637x vor

Oha !

volkard

out schrieb:

int main()
{
	map<long long,map<long long,long long>> zyklen_laengen;

	long long begin_startzahl   = 1;
	long long begin_spiegelzahl = 65530;

	long long end_startzahl     = begin_spiegelzahl; // end = ausschliesslich
	long long end_spiegelzahl   = 65541;

	for(long long startzahl=begin_startzahl; startzahl!=end_startzahl; ++startzahl)
	{
		for(long long spiegelzahl=begin_spiegelzahl; spiegelzahl!=end_spiegelzahl; ++spiegelzahl)
		{
			++zyklen_laengen[ spiegelzahl ][ finde_zyklus_laenge(startzahl,spiegelzahl) ];
		}
	}

	for(const auto& p : zyklen_laengen)
	{
		cout << "Alle Zykluslaengen der Spiegelzahl " << p.first << ':' << '\n';

		for(const auto& m : p.second)
		{
			cout << "Zykluslaenge " << m.first << " kommt " << m.second << "x vor" << '\n';
		}
		cout << '\n';
	}
}

würde ich schreiben als

int main() 
{
	long long begin_spiegelzahl = 65530;
	long long end_spiegelzahl   = 65541;

	for(long long spiegelzahl=begin_spiegelzahl; spiegelzahl!=end_spiegelzahl; ++spiegelzahl) 
	{
		map<long long,long long> zyklen_laengen;

		for(long long startzahl=1; startzahl!=spiegelzahl; ++startzahl) 
		{
			++zyklen_laengen[ finde_zyklus_laenge(startzahl,spiegelzahl) ];
		}

		cout << "Alle Zykluslaengen der Spiegelzahl " << spiegelzahl << ':' << '\n';
		for(const auto& m : zyklen_laengen) 
		{
			cout << "Zykluslaenge " << m.first << " kommt " << m.second << "x vor" << '\n';
		}
		cout << '\n';
	}
}

brak

@out ...

Zykluslänge ist uninteressant ohne Angabe der Zyklen selbst. Also hinter Zykluslänge 4 können sich zwei vom Zahlenbestand grundverschiedene Zyklen verbergen .... Darum ging es mir eigentlich.