System counting

Sun Dec 17 09:04:50 CET 2006

Dear Max and Seqfans,
Some more about optimalization algorhitm
1. Combining probabilistic-deterministic algorithm will be have time T_100
First steps probabilistic
t_100=Sum[Log[x]/Log[100](mod[x]),{x,1,500000000,100)]
Second steps deterministic
T_100=Sum[Log[t_100],{x,1,t_100)]
2. In binary system inspite that varying 5 digits mean 2^5=32 that  
probabilty is only 1/16
3. In system base 100 varying 3 decimal digits that mean 1,5 in system 100  
and result is exactly that same as in decimal
4. Recent question is "Does existed system in base n that varying in this  
system only one last digits ?"
BEST WISHES
ARTUR

> Dear Max,
> I have to 10^7 digits step by steps. But for system in basis 100 I'm  
> going ten times quicker as in decimal but probability of success is  
> every time 1/500
> that I have to do 10000000*500 =500 000 000 checkings where in decimal  
> these was
> 275 000 000 "only"
> Additional parameter in optimalization is time
> In 100-base system T_100=Sum[Log[x],{x,1,500000000,100)]
> in 10-base  
> T_10=Sum[Log[x],{x,1,25000000,10}]+Sum[Log[x],{x,250000000,10)]
> My problem is find as n that T_n is smallest. Optimalization problem  
> isn't linear.
> BEST WISHES
> ARTUR
>
> Dnia 16-12-2006 o 22:18:12 Max A. <maxale at gmail.com> napisał(a):
>
>> If I understood you correctly, you want to win the EFF prize for a
>> prime with 10^7 digits by finding a number of that size such that it
>> has a prime number nearby (e.g., "3 last digits varying").
>>
>> I see two problems with your arguments:
>>
>> First, it is not clear at all why only 3 last digits will be varying.
>> OK, you've got some small examples supporting this claim but examples
>> do not prove anything. Have you heard of the Law of small numbers?
>> http://mathworld.wolfram.com/StrongLawofSmallNumbers.html
>>
>> Second, even if you are correct (or lucky) to catch a prime number
>> with 10^7 digits, how you are going to prove that it is prime? What is
>> "modified Wilson-Lehmer" you are referring to? Generic deterministic
>> primality tests are not fast enough for the numbers of that size.
>> There are fast primality tests but they are probabilistic, meaning
>> that they cannot substitute a proof of primality (required by EFF).
>>
>> Max
>>
>>
>> On 12/16/06, Artur <grafix at csl.pl> wrote:
>>> Dear Seqfans,
>>> Is following optimalization problem
>>> Finding basis of counting system such that time reaching 10 000 000  
>>> digits
>>> prime by my procedure will be shortest.
>>> Formula will be follwing for my previous sequence will be:
>>> If we take counting system basis 100 3 last digits varying (see bellow)
>>> For my previous system if we go from a(odd) to a(even) one digit  
>>> varying.
>>> Probababilty of success (that we find prime) is 1/5 if we go from  
>>> a(even)
>>> to a(odd) two last digits varying and in this case probabilty is 1/50.  
>>> To
>>> reaching prime 10 000 000 digits we need 5 000 000 checkings with
>>> probability 1/5 and 5 000 000 with probability 1/50 together
>>> 5000000*5+5000000*50 = 275000000 steps. Now we take to counting that  
>>> time
>>> of checking that number is prime or not by modified Wilson-Lehmer
>>> algorithm is log(number of digits). My question is which counting  
>>> system
>>> will be the quickest one.
>>> BEST WISHES
>>> ARTUR
>>>
>>>
>>>
>>>
>>> %I A000001
>>> %S A000001 2, 199, 19891, 1989077, 198907679, 19890767893,  
>>> 1989076789283,
>>> 198907678928279, 19890767892827873, 1989076789282787297,
>>> 198907678928278729697, 19890767892827872969661,  
>>> 1989076789282787296966091,
>>> 198907678928278729696609039, 19890767892827872969660903813,
>>> 1989076789282787296966090381249, 198907678928278729696609038124829,
>>> 19890767892827872969660903812482509,  
>>> 1989076789282787296966090381248250849,
>>> 198907678928278729696609038124825084813,
>>> 19890767892827872969660903812482508481211,
>>> 1989076789282787296966090381248250848120823,
>>> 198907678928278729696609038124825084812082207,
>>> 19890767892827872969660903812482508481208220559,
>>> 1989076789282787296966090381248250848120822055831,
>>> 198907678928278729696609038124825084812082205583091,
>>> 19890767892827872969660903812482508481208220558309043,
>>> 1989076789282787296966090381248250848120822055830904249,
>>> 198907678928278729696609038124825084812082205583090424757,
>>> 19890767892827872969660903812482508481208220558309042475663
>>> %N A000001 Biggest primes <100*a[n-1] a[1]=2
>>> %F A000001 a(n) = 10*a(n-1)
>>> %Y A000001 A006902,A040016,A120031-A120041
>>> %O A000001 1
>>> %K A000001 ,nonn,
>>> %A A000001 Artur Jasinski (grafix at csl.pl), Dec 16 2006
>>> Dnia 16-12-2006 o 20:16:13 Artur <grafix at csl.pl> napisał(a):
>>>
>>> > Dear Jonathan and Others,
>>> > Binary system isn't as effective as decimal because 5 or 6 last  
>>> digits
>>> > varying
>>> > %I A000001
>>> > %S A000001
>>> > 10,11,101,111,1101,10111,10101,1010011,10100011,100111101,1001110111,
>>> >  
>>> 10011101011,100111000111,1001110001011,10011011110101,100110111100001,
>>> >  
>>> 1001101110111101,10011011101010011,100110111010011101,1001101110100011111,
>>> > 10011011101000111011,100110111010001101101,1001101110100010111111,
>>> >  
>>> 10011011101000101110101,100110111010001011010111,1001101110100010110101011,
>>> > 10011011101000101101000001,100110111010001011001110011,
>>> > 100110111010001011011100001,10011011101000101100110111001,
>>> > 100110111010001011001101010111,1001101110100010110011010010111,
>>> > 10011011101000101100110100011001,100110111010001011001101000101011,
>>> >  
>>> 1001101110100010110011010001000001,10011011101000101100110100001111001,
>>> >  
>>> 100110111010001011001101000011101111,1001101110100010110011010000110111101,
>>> >  
>>> 10011011101000101100110100001101011011,100110111010001011001101000011010110101
>>> > %N A000001 Biggest primes writen in binary system <2*a[n-1] a[1]=2
>>> > %C A000001 These sequence visualized Chebyshev low that between n  
>>> and 2n
>>> > existed minimum 1 prime
>>> > %F A000001 a(n) = 2*a(n-1)
>>> > %Y A000001 A006902,A040016,A120031-A120041
>>> > %O A000001 1
>>> > %K A000001 ,nonn,
>>> > %A A000001 Artur Jasinski (grafix at csl.pl), Dec 16 2006
>>> >
>>> > Dnia 16-12-2006 o 18:12:23 Jonathan Post <jvospost3 at gmail.com>
>>> > napisał(a):
>>> >
>>> >> "Chebychev said it and I'll say it again:
>>> >> There's always a prime between n and 2n."
>>> >>
>>> >> I skipped the attribution in A118909.*
>>> >> *
>>> >> Joseph Louis François Bertrand [1822-1900] was the Paris professor  
>>> who
>>> >> made
>>> >> the conjecture, proved by Chenychev in 1850. I have heard that It
>>> >> appears
>>> >> that Nat Fine wrote this couplet in honor of Paul Erdos.
>>> >>
>>> >> Jasinski said it, and emailed again:
>>> >> There's always a prime between n and 10n.
>>> >>
>>> >> "ten" rhymes with "n."  This is as great an advance in mathematical
>>> >> poetry
>>> >> as any sequence containing "14" is to sonnets.  Or, more to the  
>>> point,
>>> >> as
>>> >> the fact that the number of syllables in a haiku is prime.
>>> >>
>>> >> I'm nearly the last person to criticize anyone who submits a base
>>> >> sequence,
>>> >> or a sequence involving primes. But when I do, I know it to be a  
>>> base
>>> >> sequence, and endeavor to submit the more generalized sequence of
>>> >> antidiagonals of the array of such a sequence over all natural  
>>> number
>>> >> bases.
>>> >>
>>> >> Sometimes generalization sheds new light on a problem.  
>>> Grothendieck, for
>>> >> instance, as a master of that, before he turned his mind to  
>>> politics. If
>>> >> there is an enlightening generalization that moves beyond the
>>> >> arbitrariness
>>> >> on decimal base, I'd be pleased to see it.
>>> >>
>>> >> No disrespect to Jasinski.  I also have made the mistake of
>>> >> egotistically
>>> >> proposing to name something after myself (a la Donald Trump), and  
>>> over
>>> >> premature exclamation marks, not symbolizing factorials, out of
>>> >> excitement
>>> >> and enthusiam. Also, sometimes I like the sequences by this  
>>> gentleman,
>>> >> as
>>> >> indicated by A113914 and its ilk.
>>> >>
>>> >> In this holiday season, perhaps it is best to lean towards  
>>> tolerance,
>>> >> charity, forgiveness, and kindness.
>>> >>
>>> >> -- Jonathan Vos Post
>>> >>
>>> >> On 12/16/06, Hans Havermann <pxp at rogers.com> wrote:
>>> >>>
>>> >>> Antti Karttunen asked:
>>> >>>
>>> >>> So, please tell us, what is the ground-breaking idea in your primes
>>> >>> below?
>>> >>>
>>> >>>
>>> >>> 17989, 179849, 1798487, 17984833, 179848309, 1798483067,
>>> >>> 17984830667, 179848306667, 1798483066669, 17984830666651,
>>> >>> 179848306666507,
>>> >>> ...
>>> >>>
>>> >>>
>>> >>> I can at least verify that:
>>> >>>
>>> >>> a(1) = 17989
>>> >>> a(n) = PreviousPrime[10*a(n-1)]
>>> >>>
>>> >>> I hope there's more to it than that. ;)
>>> >>>
>>> >>>
>>> >
>>> >
>>> >
>>> > __________ NOD32 Informacje 1924 (20061215) __________
>>> >
>>> > Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
>>> > http://www.nod32.com lub http://www.nod32.pl
>>> >
>>>
>>>
>>>
>
>
>
> __________ NOD32 Informacje 1924 (20061215) __________
>
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> http://www.nod32.com lub http://www.nod32.pl
>