Squares

General FreeBASIC programming questions.
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 02, 2012 9:35

@ Albert.
You are correct, there are no patterns.
During the last 2500 years, thousands of mathematicians have looked for patterns.
Not one has yet found a reliable pattern.
IMO it is possible to prove mathematically that patterns are not possible.
The sieve of Eratosthenes is the only pattern.
dodicat
Posts: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Oct 02, 2012 10:23

@ Albert
The gaps between the primes are the sticking points.
You can have two primes in the billions seperated by only 2.

@ Richard
The gears ~ Probably why British Leyland went wrong.

Maybe your assumption about gaps could be proven, maybe not. But if there is no pattern between the gaps the next best thing is random even gaps which doesn't seem to ring believable.

Another branch of Number theory must be created to solve the prime number problem and I daresay that is easier said than done.

Remember that Boolean algebra sat on the shelf for decades before a use was found for it.
I don't think the Prime cruncher is on the shelf yet.

But hey ~ nobody can accuse us here in humble squares of not doing our bit.

Anyway, here's the Highest common factor (Greatest common divisor) of two numbers bloatedly done using the prime factors of each number:

Code: Select all

 

Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer
    Dim As Integer i
    #macro fill(x)
    i=Ubound(p)+1
    Redim Preserve p(1 To i)
    p(i)=x
    #endmacro
    #macro Eliminate(x)
    While number Mod x=0
        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1
    Wend
    #endmacro
    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull
   
    Eliminate(2)
    Eliminate(3)
   
    While divisor<limit
        divisor=divisor+6
        Eliminate((divisor-1))
        Eliminate((divisor+1))
    Wend
    If number>1 Then
        fill(number)
        check=check*number
    End If
    number=original
    Return check=original
End Function
Sub PrintPrimeFactors(factors() As Ulongint)
    Var msg=", ",acc=1ull
    Print
    For z As Integer=1 To Ubound(factors)
        If z<Ubound(factors) Then msg=", " Else msg=""
        acc=acc*factors(z)
        Print factors(z) & msg;
    Next z
    Print
    If Ubound(factors)=1 Then msg=" (Number is a PRIME)"
    Print "Prime factors of " & acc & msg:Print "______":Print
End Sub

Dim Shared As Integer start
Function IsIn(a() As Ulongint,num As Ulongint)As Integer
    For x1 As Integer=start+1 To Ubound(a)
        If num=a(x1) Then start=x1:Return -1
    Next x1
End Function
Function hcf(a1() As Ulongint,a2() As Ulongint) As Ulongint
    Dim As Ulongint prod=1
    For x1 As Integer=1 To Ubound(a1)
        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)
    Next x1
    start=0
    Return prod
End Function
' ============================================================
Dim As Ulongint num1,num2,h


num1=934456222228000
num2=388899002702800

Redim As Ulongint factors1(),factors2(),Hcf_factors()

If getprimefactors(num1,factors1()) Then printprimefactors(factors1())
If getprimefactors(num2,factors2()) Then printprimefactors(factors2())
h= hcf(factors1(),factors2())

Print "For ";num1;" and ";num2
Print "The Highest Common Factor = ";h
Print
Print "Prime factors of Highest common factor:"
If getprimefactors(h,Hcf_factors()) Then printprimefactors(Hcf_factors())

Print "done"
Sleep

 
albert
Posts: 4822
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Oct 02, 2012 22:50

@Dodicat

I tried some different numbers that I thought might be prime,
I don't know if they are or not, but your code returns a similar set of values for each.

Code: Select all



Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer
    Dim As Integer i
    #macro fill(x)
    i=Ubound(p)+1
    Redim Preserve p(1 To i)
    p(i)=x
    #endmacro
    #macro Eliminate(x)
    While number Mod x=0
        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1
    Wend
    #endmacro
    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull
   
    Eliminate(2)
    Eliminate(3)
   
    While divisor<limit
        divisor=divisor+6
        Eliminate((divisor-1))
        Eliminate((divisor+1))
    Wend
    If number>1 Then
        fill(number)
        check=check*number
    End If
    number=original
    Return check=original
End Function
Sub PrintPrimeFactors(factors() As Ulongint)
    Var msg=", ",acc=1ull
    Print
    For z As Integer=1 To Ubound(factors)
        If z<Ubound(factors) Then msg=", " Else msg=""
        acc=acc*factors(z)
        Print factors(z) & msg;
    Next z
    Print
    If Ubound(factors)=1 Then msg=" (Number is a PRIME)"
    Print "Prime factors of " & acc & msg:Print "______":Print
End Sub

Dim Shared As Integer start
Function IsIn(a() As Ulongint,num As Ulongint)As Integer
    For x1 As Integer=start+1 To Ubound(a)
        If num=a(x1) Then start=x1:Return -1
    Next x1
End Function
Function hcf(a1() As Ulongint,a2() As Ulongint) As Ulongint
    Dim As Ulongint prod=1
    For x1 As Integer=1 To Ubound(a1)
        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)
    Next x1
    start=0
    Return prod
End Function
' ============================================================
Dim As Ulongint num1,num2,h


'num1=934456222228000
'num2=388899002702800

num1=10000000000000001
num2=30000000000000003

Redim As Ulongint factors1(),factors2(),Hcf_factors()

If getprimefactors(num1,factors1()) Then printprimefactors(factors1())
If getprimefactors(num2,factors2()) Then printprimefactors(factors2())
h= hcf(factors1(),factors2())

Print "For ";num1;" and ";num2
Print "The Highest Common Factor = ";h
Print
Print "Prime factors of Highest common factor:"
If getprimefactors(h,Hcf_factors()) Then printprimefactors(Hcf_factors())

Print "done"
Sleep
 
Destructosoft
Posts: 88
Joined: Apr 03, 2011 3:44
Location: Inside the bomb
Contact:

Re: Squares

Postby Destructosoft » Oct 02, 2012 23:59

Richard wrote: it is possible to prove mathematically that patterns are not possible.
The sieve of Eratosthenes is the only pattern.
Obviously that's a contradiction. Either the sieve is a pattern and therefore patterns are possible, or patterns are NOT possible and therefore the sieve is not a pattern.
dodicat
Posts: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Oct 03, 2012 0:10

Hi Albert.
Looks ok.
Remember that the (highest common factor) prime factors are those factors which are common to the prime factors of each number.
It is an intersection of the prime factors for each number
2 2 5 7 11 23 101
and
2 2 2 3 7 17 23 103
the intersection is
2 2 7 23


If you check all the prime factors shown for numbers you should be able to distinguish them.

I've been thinking again about the sequences of numbers for these primes, the only way to get them seems is to evolve them (in the year 2012 anyway).
A bit like the Fibonacci sequence ~ loosly
But SEEMS is the keyword here.
Anyway, I've obtained the Highest common factor the other way here.
That is find ALL the factors for each number and get the (Highest COMMON factor to each group)
It's still bloatware, but I'm getting a bit fed up with prime numbers now.
In this one you enter your numbers at runtime, more than two if you wish.

Code: Select all


Sub AllFactors(N As Ulongint,factors() As Ulongint)  'partially optimized
    #macro bsort(array)
    For p1 As Integer  = 1 To Ubound(array) - 1
        For p2 As Integer  = p1 + 1 To Ubound(array) 
            If array(p1)>array(p2) Then Swap array(p1),array(p2)
        Next p2
    Next p1
    #endmacro   
    Dim As Ulongint c
    For i As Ulongint = 1 To Sqr(N)       
        If N Mod i=0 Then
            C += 1
            Redim Preserve factors(c)
            factors(c)=i
            If N <> i^2 Then
                C += 1
                Redim Preserve factors(c)
                factors(c)=n\i
            End If
        End If
    Next i
    bsort(factors)
End Sub

Function hcf(num1 As Ulongint,num2 As Ulongint) As Ulongint
    Redim As Ulongint A1(),A2()
    AllFactors(num1,A1())
    AllFactors(num2,A2())
    Dim As Ulongint max=1
    For x1 As Integer=1 To Ubound(a1)
        For x2 As Integer=1 To Ubound(a2)
            If a1(x1)=a2(x2) Then
                max=a1(x1)
            End If
        Next x2
    Next x1
    Return max
End Function

' =============================================================

Dim As Ulongint number,x,lcm

Print "More than two numbers if you wish, enter 0 to end the inputs"
Print
Input "FIRST NUMBER ";number
lcm=number
Do
    Input " Next number ";x
    If x>0 Then
        number=hcf(number,x)
        lcm=lcm*x\hcf(lcm,x)
    End If
Loop Until x=0
Print
Print "HCF = ";number
Print "LCM = ";lcm
Sleep

 
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 03, 2012 4:16

@ Destructosoft.

Define Pattern.

Albert is looking for patterns in the digits when primes are written in base 10. Since primes are more fundamental than the base 10 number system, I cannot see how that could possibly work without writing the number n in every prime base below Sqrt(n) and looking for one representation that ends in zero. That is more effort than factorising.

Generating primes with a sieve is the only “patterned” way of finding primes. Given an arbitrary number you must advance the sieve to that number, which is again, factorising.

The tool called a sieve has a pattern. Prime numbers do not.
albert
Posts: 4822
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Oct 03, 2012 19:37

@Richard
It may be that; there are no patterns in Prime numbers.
But some patterns are so complex , like tree bark , dog , cat or cow or butterfly color patterns.

I imagine there is either a single whole pattern, or possibly many different interacting patterns.

Thats why i had thought to sort the primes into their ending digits and check values and gaps,
but I found no immediatley apparent pattern.

It may be that there is some type of Space-Time wormhole patterns that go into a wormhole at one number and come out further down the numberline.
albert
Posts: 4822
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Oct 03, 2012 23:21

@Richard
@Dodicat
I found some patterns!!!! in lucky 7's
First; you have to dick with the "filename" var to point to your file with primes 1 to ??

First it stops at 14 and then every 7.
Just space through and watch the greens and blues making the patterns. (some don't have a 7 or 14 pattern.)
The first pattern centers at 7 and goes center -7 to center +7 (The patterns aren't sequential they are MIRRORED.)

Code: Select all

'===============================================================================       
'===============================================================================       
#include "file.bi"
'===============================================================================       
'===============================================================================       
'Get Primes from file
'===============================================================================       
'===============================================================================       
dim as ulongint low  =          1
dim as ulongint high = 100000
'===============================================================================
dim as string filename = "C:\USB\MY-FB-PROGRAMS-023\Prime-Numbers\PRIMES\" + str(low) + "_" + str(high) + ".txt"
if not FileExists(filename) then
    color 14
        print "File Name Doesnt' Exist."
        print
        print "Press a key to END."
    color 7
    sleep
    end
end if
redim as string Primes(0 to high)
dim as string inputs
dim as ulongint count
open filename for input as #1
    do
        input #1,inputs
        count = val(inputs)
        Primes(count) = inputs   
    loop until eof(1)
close #1
Print "Got Primes form file, Press a key to start.."
sleep

'===============================================================================
'===============================================================================
redim as string others(0 to high)
for a as ulongint = 0 to high
    others(a) = str(a)
    if Primes(a) <> "" then others(a)=""
next

dim as ulongint n,n1
dim as double Remainder
dim as string num1 , a1
dim as ulongint mods=14
for a as ulongint = 0 to ubound(Primes)
    num1=others(a)
    if num1="" then num1 = Primes(a)
    'if right(num1,1)<>"0" then
    'if right(num1,1)<>"2" then
    'if right(num1,1)<>"4" then
    'if right(num1,1)<>"5" then
    'if right(num1,1)<>"6" then
    'if right(num1,1)<>"8" then
    Remainder = 0
    for n1 = 1 to len(num1) step 1
        for n = 1 to n1 step 1
            a1 = str( abs( cint(num1[n1-1]-48) - cint(num1[n-1]-48) ) )
            a1 = a1 + string(len(num1)+len(num1)-n-n1,"0")
            Remainder = (Remainder + (valulng(a1) ))
        next
    next
    if others(a) = "" then color 9 : print "Prime = " ; num1 , "Remainder = " ; remainder , "Diff = " ; (remainder ) + val(num1)  : color 7
    if others(a)<> "" then color 10: print "Other = " ; num1 , "Remainder = " ; remainder , "Diff = " ; (remainder ) + val(num1) : color 7
    'sleep 1000
    'end if
    'end if
    'end if
    'end if
    'end if
    'end if
    if val(num1)<>0 and val(num1) mod mods = 0 then sleep : cls : mods+=7
next
'===============================================================================   
'===============================================================================   
'End Program
'===============================================================================   
'===============================================================================   
sleep
END



@Dodicat
How do we make a program for detecting the mirrored pattterns.
It might be that they are mirrored with infinity, where infinity is not prime while infinity -1 is prime.
But my prediction is that there are certain numbers where the mirroring begins and ends,
where you have centers mod 7 = 0 and the mirroring goes center - ?? to center + ??
without overlapping other mirrored sections.
But the patterns require using the whole shebang input of; both composites and primes.
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 04, 2012 4:49

@ dodicat.
Here is a gcd by factorisation.
How should I walk along the final two lists of factors rather than For ia, For ib rectangular search.

Code: Select all

'=======================================================================
' Factorise a 64 bit Unsigned Long Integer
'=======================================================================
Type factor_table               ' 216 bytes = 8 + 8*16 + 4*16 + 4 + 8
    number As Ulongint          ' the input number to factorise
    prime(0 To 15) As Ulongint  ' prime factors found, maximum possible = 15
    count(0 To 15) As Integer   ' repeat count for each prime factor found
    nf As Integer               ' the number of different prime factors found
    seconds As Double           ' time in seconds used for the factorisation
End Type

Declare Sub Show_factors(Byref As factor_table)
Declare Sub factors(     Byref As factor_table)

'=======================================================================
' find GCD using factor tables
'=======================================================================
Randomize Timer * 1e6
Dim As factor_table a, b    ' object to hold input and outputs

a.number = Rnd * 100 + 1000
factors(a)
show_factors(a)

b.number = Rnd * 100 + 1000
factors(b)
show_factors(b)

Dim As Integer count, gcd = 1
For ia As Integer = 1 To a.nf
    For ib As Integer = 1 To b.nf
        If a.prime(ia) = b.prime(ib) Then
            count = a.count(ia)
            If b.count(ib) < count Then count = b.count(ib)
            For i As Integer = 1 To count
                gcd *= a.prime(ia)
            Next i
        End If
    Next ib
Next ia

Print " GCD ="; gcd

Print "              All done."

'=======================================================================
' macro used by factorisation routine
'=======================================================================
#macro divisor_step(skip)   ' test if this trial divisor is a factor of number
divisor += skip
Do
    residue = num Mod divisor   ' remainder of this trial division
    If residue = 0 Then         ' a factor has been found
        If .prime(.nf) = divisor Then  ' previous prime factor repeats
            .count(.nf) += 1
        Else                    ' a new factor has been found
            .nf += 1            ' initiate a new factor entry
            .prime(.nf) = divisor
            .count(.nf) = 1
        End If
        num = num \ divisor     ' remove the factor
        limit = Sqr(num)        ' move the limit down
    End If
Loop Until residue <> 0         ' finished repeats of this divisor
#endmacro

'=======================================================================
' factorisation routine
'=======================================================================
Sub factors( Byref table As factor_table )
    With table
        .seconds = Timer
        .nf = 0   ' number of different factors found so far
        Dim As Ulongint num = .number, residue
        Dim As Ulongint divisor = 0, limit = Sqr(num)
        ' start with the silly test
        If num < 2 Then     ' zero and one default here to prime because,
            .nf = 1         '  they have only one entry in the table,
            .count(1) = 1   '   they have a count of one, and that one
            .prime(1) = num '    factor's value is equal to the number.
            .seconds = 0
        Else
            ' then small prime divisors
            divisor_step(2)  ' test  2
            divisor_step(1)  ' test  3
            divisor_step(2)  ' test  5
            divisor_step(2)  ' test  7
            Do  ' then full ahead with a repeat cycle of ( 2 * 3 * 5 ) = 30
                divisor_step(4)   ' 11   41   71   101   131 note:
                divisor_step(2)   ' 13   43   73   103   133  that
                divisor_step(4)   ' 17   47   77   107   137  each
                divisor_step(2)   ' 19   49   79   109   139  column
                divisor_step(4)   ' 23   53   83   113   143  rises by
                divisor_step(6)   ' 29   59   89   119   149  the repeat
                divisor_step(2)   ' 31   61   91   121   151  cycle's period
                divisor_step(6)   ' 37   67   97   127   157  of thirty 
                ' check once every cycle of 30 to detect number is a prime
                If divisor > limit Then ' the number remaining must be prime
                    If num > 1 Then
                        .nf += 1
                        .prime(.nf) = num
                        .count(.nf) = 1
                    End If
                    Exit Do
                End If
            Loop Until num = 1
            .seconds = Timer - .seconds
        End If
    End With
End Sub

'=======================================================================
' display the list of factors found
'=======================================================================
Sub Show_factors(Byref table As factor_table)
    With table
        Print .number; " = ";
        For i As Integer = 1 To .nf
            If i > 1 Then Print " x ";
            Print .prime(i);
            If .count(i) > 1 Then Print "^" & .count(i);
        Next i
        If (.nf = 1) And (.count(1) = 1)  Then
            Color 13 : Print " is prime. "; : Color 7
        End If
    End With
    Print
End Sub

'=======================================================================
Sleep
'=======================================================================

dodicat
Posts: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Postby dodicat » Oct 04, 2012 10:31

Richard/Albert
I've tried various methods myself to elegantize the intersection of two sets of numbers.
Pascal and other languages have some SET functions inbuilt.
I tried using the bubblesort algo where every element comes into contact with every element in a single array - extended to two arrays, I was nearly there at one stage.
Unions and intersections and other SET operations would be a little project worth fiddelling with in FreeBASIC, maybe it's been done somewhere in the forum already?

The next step to perform is getting all factors of a number from prime factors of a number.
With say N prime factors 2^N -1 combinations would be possible - (~ I RECKON) - but some of these could well be duplicates and would have to be weeded out.

Anyway, I've updated my own HCF of two or more numbers, using prime factors. I think they call something like this PROCRASTINATION.

The LCM of numbers within ulongint can very quickly go out of bounds, so I've tentatively just used a double for this.

Code: Select all

 

Function getprimefactors(number As Ulongint,p() As Ulongint) As Integer
    Dim As Integer i
    #macro fill(x)
    i=Ubound(p)+1
    Redim Preserve p(1 To i)
    p(i)=x
    #endmacro
    #macro Eliminate(x)
    While number Mod x=0
        number=number\x :fill(x):check=check*x:limit=Sqr(number)+1
    Wend
    #endmacro
    Dim As Ulongint original=number,divisor=0ull,limit=Sqr(number)+1,check=1ull
   
    Eliminate(2)
    Eliminate(3)
   
    While divisor<limit
        divisor=divisor+6
        Eliminate((divisor-1))
        Eliminate((divisor+1))
    Wend
    If number>1 Then
        fill(number)
        check=check*number
    End If
    number=original
    Return check=original
End Function
Sub PrintPrimeFactors(factors() As Ulongint)
    Var msg=", ",acc=1ull
    Print
    For z As Integer=1 To Ubound(factors)
        If z<Ubound(factors) Then msg=", " Else msg=""
        acc=acc*factors(z)
        Print factors(z) & msg;
    Next z
    Print
    If Ubound(factors)=1 Then msg=" (Number is a PRIME)"
    Print "Prime factors of " & acc & msg:Print "______":Print
End Sub

Dim Shared As Integer start
Function IsIn(a() As Ulongint,num As Ulongint)As Integer
    For x1 As Integer=start+1 To Ubound(a)
        If num=a(x1) Then start=x1:Return -1
    Next x1
End Function
Function hcf(num1 as Ulongint,num2 As Ulongint) As Ulongint
    redim as ulongint a1(),a2()
    getprimefactors(num1,a1())
    getprimefactors(num2,a2())
    Dim As Ulongint prod=1
    For x1 As Integer=1 To Ubound(a1)
        If IsIn(a2(),a1(x1)) Then  prod=prod*a1(x1)
    Next x1
    start=0
    Return prod
End Function
' ============================================================

dim as ulongint number,x',lcm 'optional ulongint or double for lcm
dim as double lcm
Print "More than two numbers if required, enter 0 to end inputs"
print
input "FIRST NUMBER ";number
lcm=number
do
    input " Next number ";x
    if x>0 then
        number=hcf(number,x)
        lcm=lcm*(x\hcf(lcm,x))
    end if
loop until x=0
print
print "HCF = ";number
print "LCM = ";lcm
print "-------- Press a key --------------------------------"
sleep
'=========================================
'OR JUST FOR HCF OF TWO NUMBERS ----
dim as ulongint n1,n2,gcd
redim as ulongint f1(),f2(),f3()
n1=56778855490064
n2=6677554440024
if GetPrimeFactors(n1,f1()) then PrintPrimeFactors(f1())
if GetPrimeFactors(n2,f2()) then PrintPrimeFactors(f2())
gcd=hcf(n1,n2)
print "HCF of ";n1;" and ";n2;" = ";gcd
if GetPrimeFactors(gcd,f3()) then PrintPrimeFactors(f3())
sleep
 
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 04, 2012 11:24

@ dodicat.
I think I solved it. Since my prime factor lists are already sorted it turns out that it is easy to walk the walk.
dodicat wrote:The LCM of numbers within ulongint can very quickly go out of bounds
By using Ulongint for the GCD there should be no overflow when building the GCD of two Ulongint numbers. It must be smaller than or equal to the smaller of the input numbers.
Here is my revised code.

Code: Select all

'=======================================================================
' Find GCD from Factors.
'=======================================================================
Type factor_table               ' 216 bytes = 8 + 8*16 + 4*16 + 4 + 8
    number As Ulongint          ' the input number to factorise
    prime(0 To 15) As Ulongint  ' prime factors found, maximum possible = 15
    count(0 To 15) As Integer   ' repeat count for each prime factor found
    nf As Integer               ' the number of different prime factors found
    seconds As Double           ' time in seconds used for the factorisation
End Type

Declare Sub      factors(Byref As factor_table)
Declare Sub Show_factors(Byref As factor_table)

'=======================================================================
' find GCD using factor tables
'=======================================================================
Randomize Timer * 1e6
Dim As factor_table a, b    ' object to hold input and outputs

a.number = Rnd * 100 + 1000
factors(a)
show_factors(a)

b.number = Rnd * 100 + 1000
factors(b)
show_factors(b)

Dim As Ulongint gcd = 1
Dim As Integer count, ia = 1, ib = 1

Do
    If a.prime(ia) = b.prime(ib) Then
        count = a.count(ia)
        If b.count(ib) < count Then count = b.count(ib)
        For i As Integer = 1 To count
            gcd *= a.prime(ia)
        Next i
        ia += 1
        ib += 1
    Else
        If a.prime(ia) < b.prime(ib) Then
            ia += 1
        Else
            ib += 1
        End If
    End If
Loop Until (ia > a.nf) Or (ib > b.nf)

Print " GCD = "; gcd

Print "              All done."


'=======================================================================
' Factorise a 64 bit Unsigned Long Integer
'=======================================================================
' macro used by factorisation routine
'=======================================================================
#macro divisor_step(skip)   ' test if this trial divisor is a factor of number
divisor += skip
Do
    residue = num Mod divisor   ' remainder of this trial division
    If residue = 0 Then         ' a factor has been found
        If .prime(.nf) = divisor Then  ' previous prime factor repeats
            .count(.nf) += 1
        Else                    ' a new factor has been found
            .nf += 1            ' initiate a new factor entry
            .prime(.nf) = divisor
            .count(.nf) = 1
        End If
        num = num \ divisor     ' remove the factor
        limit = Sqr(num)        ' move the limit down
    End If
Loop Until residue <> 0         ' finished repeats of this divisor
#endmacro

'=======================================================================
' factorisation routine
'=======================================================================
Sub factors( Byref table As factor_table )
    With table
        .seconds = Timer
        .nf = 0   ' number of different factors found so far
        Dim As Ulongint num = .number, residue
        Dim As Ulongint divisor = 0, limit = Sqr(num)
        ' start with the silly test
        If num < 2 Then     ' zero and one default here to prime because,
            .nf = 1         '  they have only one entry in the table,
            .count(1) = 1   '   they have a count of one, and that one
            .prime(1) = num '    factor's value is equal to the number.
            .seconds = 0
        Else
            ' then small prime divisors
            divisor_step(2)  ' test  2
            divisor_step(1)  ' test  3
            divisor_step(2)  ' test  5
            divisor_step(2)  ' test  7
            Do  ' then full ahead with a repeat cycle of ( 2 * 3 * 5 ) = 30
                divisor_step(4)   ' 11   41   71   101   131 note:
                divisor_step(2)   ' 13   43   73   103   133  that
                divisor_step(4)   ' 17   47   77   107   137  each
                divisor_step(2)   ' 19   49   79   109   139  column
                divisor_step(4)   ' 23   53   83   113   143  rises by
                divisor_step(6)   ' 29   59   89   119   149  the repeat
                divisor_step(2)   ' 31   61   91   121   151  cycle's period
                divisor_step(6)   ' 37   67   97   127   157  of thirty 
                ' check once every cycle of 30 to detect number is a prime
                If divisor > limit Then ' the number remaining must be prime
                    If num > 1 Then
                        .nf += 1
                        .prime(.nf) = num
                        .count(.nf) = 1
                    End If
                    Exit Do
                End If
            Loop Until num = 1
            .seconds = Timer - .seconds
        End If
    End With
End Sub

'=======================================================================
' display the list of factors found
'=======================================================================
Sub Show_factors(Byref table As factor_table)
    With table
        Print .number; " = ";
        For i As Integer = 1 To .nf
            If i > 1 Then Print " x ";
            Print .prime(i);
            If .count(i) > 1 Then Print "^" & .count(i);
        Next i
        If (.nf = 1) And (.count(1) = 1)  Then
            Print " is prime. ";
        End If
    End With
    Print
End Sub

'=======================================================================
Sleep
'=======================================================================
albert
Posts: 4822
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Oct 04, 2012 17:53

What code are you guys using to find Primes now??

=======================================================================================
Mine is still doing divisions up to the value.
I'll stick your guys's faster code into my pattern searcher, instead of pulling the Primes from a file.
=======================================================================================

If it pans out, you'll be able to say that :

"NumX" is in the "Nth" pattern and that pattern centers at "Y" and goes "+- N" and follows formula "F_n"

It seems that the primes and composites together, make a map fold, accordian type , of mirroring,
Where you have a center at a peak and it mirrors on the other side of the fold.
But some of the folds seems to be differing sizes???
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 04, 2012 19:31

@ Albert.
I use this prime finder code. Set the maximum nmax to trade number of primes with time.

Code: Select all

'=======================================================================
' Pretty Fast "Sieve of Eratosthenes" Prime Generator
' the primes found are saved in primes(1 to np)
' for the range from 2 to nmax, where nmax has a maximum of about 10^8
' nMax       np     time       prime %
'   10        4      2 usec     40.0
'  100       25      4 usec     25.0
'   1k      168     19 usec     16.8
'  10k     1229    180 usec     12.29
' 100k     9592    2.2 msec      9.59
'   1M    78498     28 msec      7.84
'  10M   664579    335 msec      6.65
' 100M  5761455    3.7 sec       5.76
'
'=======================================================================
Dim Shared As Integer nmax = 12750 '1e2    ' the range maximum number
Dim Shared As Integer np    ' the number of primes found that are <= nmax
Redim Shared As Integer primes(0 To nmax) ' final size is primes(1 to np)
'-----------------------------------------------------------------------
Sub generate_primes
    np = 0
    Dim As Integer i, k
    For k = 2 To nmax
        If primes(k) = 0 Then
            np += 1
            primes(np) = k
            For i = 2*k To nmax Step k
                primes(i) = 1
            Next i
        End If
    Next k
    Redim Preserve primes(np)
End Sub

'-----------------------------------------------------------------------
' test the sub
Dim As Double t = Timer
generate_primes
t = Timer - t
Print np; " primes found up to"; nmax;
Print Using " in###.###### seconds."; t

' display only the largest 100 found
Dim As Integer first = np - 100
If first < 1 Then first = 1
For i As Integer = first To np
    Print primes(i),
Next i

'=======================================================================
Print " All done."
Sleep
'=======================================================================

albert
Posts: 4822
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Postby albert » Oct 04, 2012 21:00

@Richard
Thanks !! Thats alot faster than all the divisions.
Richard
Posts: 2942
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Postby Richard » Oct 04, 2012 21:07

And it is not even an optimised version!

Return to “General”

Who is online

Users browsing this forum: No registered users and 4 guests