The idea is to submit sets of numbers so their combination by addition and subtraction generates the most distinct primes. There are 12 problems, for sets of 3 to 14 numbers.
A pen and paper should be sufficient to find the optimal solution for 3 numbers. Don't be fooled however, the solutions for 4+ require a program to search through the possibilities.
4 yields easily to a computer search with at least three optimal solutions waiting to be discovered. Despite writing a program which tests 280,000 potential solutions per second, I haven't found the top solution for 5.
Currently I'm restricting the search space to one odd number, one multiple of 6 and the remaining numbers all multiples of 30. Maybe this is too restrictive?
Here's the program I'm using. Any suggestions how I can improve the speed?
n1 equ 1 n2 equ 6 n3 equ 30 n4 equ 90 n5 equ 270 i1 equ 600 i2 equ 600 vprime equ 7000 numb equ 5 ; *** generate list of primes mov si,prime+4 mov bx,5 nextpr: mov di,prime+2 try: mov ax,bx xor dx,dx div word[di] or dx,dx jz notpr scasw ja try mov word[si],bx cmpsw notpr: inc bx inc bx cmp si,prime+vprime jne nextpr ; *** fill prime table with zero xchg ax,bx mov di,tabl xchg ax,cx xor ax,ax rep stosb ; *** update values to test testnew: add word[xa],2 cmp word[xa],n1+i1+10 jc gogo mov word[xa],n1 add word[xb],6 cmp word[xb],n2+i2+10 jc gogo mov word[xb],n2 add word[xc],30 mov ax,word[xc] cmp ax,word[xd] jc gogo mov word[xc],n3 add word[xd],30 mov ax,word[xd] cmp ax,word[xe] jc gogo mov word[xd],n4 add word[xe],30 ; *** mark primes in table gogo: mov ax,word[xa] add ax,word[xe] add ax,word[xd] add ax,word[xc] add ax,word[xb] xchg dx,ax mov si,prime ptab: lodsw cmp dx,ax jc fini add ax,tabl xchg bx,ax mov byte[bx],1 cmp si,prime+vprime jne ptab fini: ; *** test xor bp,bp mov ax,word[xa] mov bx,word[xe] mov cx,word[xd] mov dx,word[xc] mov di,word[xb] call x2 ; *** if there's a new top score... xchg ax,bp cmp ax,word[xhigh] jl next ; *** ... display the winning numbers mov word[xhigh],ax call printdec mov dl,' ' call printchar mov dl,'-' call printchar mov cx,numb lea si,word[xa] disp: mov dl,' ' call printchar lodsw call printdec loop disp mov dl,0D call printchar mov dl,0A call printchar ; *** and repeat next: mov ah,1 int 016h jz redo int 020h redo: jmp testnew x2: push ax add ax,bx call x3 pop ax push ax sub ax,bx call x3 pop ax x3: push ax add ax,cx call x4 pop ax push ax sub ax,cx call x4 pop ax x4: push ax add ax,dx call x5 pop ax push ax sub ax,dx call x5 pop ax x5: push ax add ax,di call x6 pop ax push ax sub ax,di call x6 pop ax x6: xabs: neg ax js xabs add ax,tabl xchg ax,si cmp byte[si],0 je notprx inc bp mov byte[si],0 notprx: xchg ax,si ret ; *** print number in ax printdec: push ax push cx push dx mov cx,10 xor dx,dx div cx test ax,ax je pdbye call printdec pdbye: add dl,'0' call printchar pop dx pop cx pop ax ret printchar: mov ah,2 int 021 ret xhigh:dw 0 xa:dw n1-2 xb:dw n2 xc:dw n3 xd:dw n4 xe:dw n5 prime: dw 2 dw 3 tabl equ prime+vprime+10
No comments:
Post a Comment
Note: only a member of this blog may post a comment.