wieviele zahlen braucht man?
-
Erste Idee: Nimm k = [sqrt(n)] und alle Vielfachen von k kleiner als n und dazu alle natürlichen Zahlen kleiner als n. Das wären dann etwa 2*sqrt(n) Zahlen.
-
ja die idee hatte ich auhc, aber das ist mit absolter sicherheit nicht die kleinste menge...
und ich suche die kleinste menge
-
MamboKurt schrieb:
ja die idee hatte ich auhc, aber das ist mit absolter sicherheit nicht die kleinste menge...
und ich suche die kleinste mengedie Binärdarstellung ist das Beste was man hier
erreichen kann. Dann brauchst du höchstens ceiling(log(n)+1) Zahlen.
Das läßt sich auch sehr einfach beweisen.oder möchtest du in deiner Addition immer nur zwei Operanden haben?
Viele Grüße
Fischi
-
immer nur zwei operanden.
und was heißt das "ceiling" bei ceiling(log(n)+1)?
-
MamboKurt schrieb:
immer nur zwei operanden.
und was heißt das "ceiling" bei ceiling(log(n)+1)?ceiling = aufrunden
hmm, man könnte dfgdfgfd Variante noch etwas verbessern indem man
alle Zahlen 0,..,m nimmt und dann m,2m+1,3m+2,...,km+k-1>=n-m
Das optimale m könnte man auch relativ leicht ausrechnen.
Optimal ist das aber sicher nicht...Viele Grüße
Fischi
-
naja also ich schreib erstmal n prog des den ganzen scheiß durchtestet und mir dann am ende sagt, wieviele zahlen ich minimal brauch für bestimmte n. bruteforce herrscht!!!
aus den werten wird sich dann hoffentlich irendeine funktion erkennen lassen. wenn ich keine erkenne poste ich die ergebnisse einfach mal hier rein...
danach sollte man eigentlich auf einen mathematischen beweis kommen.....hoffe ich
-
Ich vermute [sqrt(n)]+1
-
das wäre auf jedenfalls zu rein kombinatorisch kleinste anzahl
-
ich habe mal die ersten Optimalwerte bestimmt und das Ergebnis dort:
http://www.research.att.com/~njas/sequences/index.html
eingegeben.
Deine gesuchte Folge ist unter A066063 verzeichnet.
Als weitere Bemerkungen stand dabei:
ID Number: A066063
URL: http://www.research.att.com/projects/OEIS?Anum=A066063
Sequence: 1,2,2,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,8,8
Name: Size of the smallest subset S of T={0,1,2,...,n} such that each element
of T is the sum of two elements of S.
Comments: If one counts all subsets S of T={0,1,2,...n} such that each number in T
is the sum of two elements of S, sequence A066062 is obtained.
Since each k-subset of S covers at most binom(k + 1, 2) members of T, we
have binom(A066063(n) + 1, 2) >= n + 1. It follows that A002024(n-1)
is a lower bound. - Rob Pratt (Rob.Pratt(AT)sas.com), May 14 2004
Example: For n=2, it is clear that S={0,1} is the unique subset of {0,1,2} that
satisfies the definition, so a(2)=2.
See also: A066062
Cf. A002024.
Adjacent sequences: A066060 A066061 A066062 this_sequence A066064
A066065 A066066
Sequence in context: A098388 A094235 A062571 this_sequence A071868
A082447 A000720
Keywords: nonn
Offset: 0
Author(s): John W. Layman (layman(AT)math.vt.edu), Dec 01 2001Viele Grüße
Fischi
-
cool
thx