Rare numbers: Difference between revisions

Line 4,233:

for over 30% of the run time. Improvements welcome: run p -d test, examine the list.asm produced from this source, and discuss or

make suggestions on [[User_talk:Petelomax|my talk page]].

<lang Phix>~~constant maxDigits = 15~~

with javascript_semantics

constant maxDigits = iff(platform()=JS?10:15)

enum COEFF, TDXA, TDXB -- struct term = {atom coeff, integer idxa, idxb}

-- (see allTerms below)

enum COEFF, TDXA, TDXB -- struct term = {atom coeff, integer idxa, idxb}

integer nd, -- number of digits

-- (see allTerms below)

count -- of solutions found earlier, for lower nd

integer nd, -- number of digits

sequence rares -- (cleared after sorting/printing for each nd)

count -- of solutions found earlier, for lower nd

sequence rares -- (cleared after sorting/printing for each nd)

function to_atom(sequence digits)

-- convert digits array to an atom value

function to_atom(sequence digits)

atom r = 0

-- convert digits array to an atom value

for i=1 to length(digits) do

atom r = 0

r = r * 10 + digits[i]

for i=1 to length(digits) do

end for

r = r * 10 + digits[i]

return r

end for

end function

return r

end function

-- psq eliminates 52 out of 64 of numbers fairly cheaply, which translates

-- to approximately 66% of numbers, or around 10% off the overall time.

-- psq eliminates 52 out of 64 of numbers fairly cheaply, which translates

-- NB: only tested to 9,007,199,254,740,991, then again I found no more new

-- to approximately 66% of numbers, or around 10% off the overall time.

-- bit patterns after just 15^2.

-- NB: only tested to 9,007,199,254,740,991, then again I found no more new

-- bit patterns after just 15^2.

constant psq = int_to_bits(#02030213,32)& -- #0202021202030213 --> bits,

int_to_bits(#02020212,32) -- in 32/64-bit compatible way.

constant psq = int_to_bits(#02030213,32)& -- #0202021202030213 --> bits,

int_to_bits(#02020212,32) -- in 32/64-bit compatible way.

function isSquare(atom n) -- determine if n is a perfect square or not

if psq[and_bits(n,63)+1] then

function isSquare(atom n) -- determine if n is a perfect square or not

atom r = floor(sqrt(n))

if psq[and_bits(n,63)+1] then

return r * r = n

atom r = floor(sqrt(n))

end if

return r * r = n

return false

end if

end function

return false

end function

procedure fnpr(integer level, atom nmr, sequence di, dis, candidates, indices, fml, dmd)

-- generate (n+r) candidates from (n-r) candidates

procedure fnpr(integer level, atom nmr, sequence di, dis, candidates, indices, fml, dmd)

if level>length(dis) then

-- generate (n+r) candidates from (n-r) candidates

sequence digits = repeat(0,nd)

if level>length(dis) then

-- (the precise why of how this populates digits has eluded me...)

sequence digits = repeat(0,nd)

integer {a,b} = indices[1],

-- (the precise why of how this populates digits has eluded me...)

c = candidates[1]+1,

integer {a,b} = indices[1],

d = di[1]+1

c = candidates[1]+1,

digits[a] = fml[c][d][1]

d = di[1]+1

digits[b] = fml[c][d][2]

digits[a] = fml[c][d][1]

integer le = length(di)

digits[b] = fml[c][d][2]

if remainder(nd,2) then

integer le = length(di)

d = floor(nd/2)+1

if remainder(nd,2) then

digits[d] = di[le]

d = floor(nd/2)+1

le -= 1

digits[d] = di[le]

end if

le -= 1

for dx=2 to le do

end if

{a,b} = indices[dx]

for dx=2 to le do

c = candidates[dx]+10

{a,b} = indices[dx]

d = di[dx]+1

c = candidates[dx]+10

digits[a] = dmd[c][d][1]

d = di[dx]+1

digits[b] = dmd[c][d][2]

digits[a] = dmd[c][d][1]

end for

digits[b] = dmd[c][d][2]

atom npr = nmr + to_atom(reverse(digits))*2 -- (npr == 'n + r')

end for

if isSquare(npr) then

atom npr = nmr + to_atom(reverse(digits))*2 -- (npr == 'n + r')

rares &= to_atom(digits)

if isSquare(npr) then

-- (note this gets overwritten by sorted set:)

rares &= to_atom(digits)

printf(1,"working... %2d: %,d\r", {count+length(rares),rares[$]})

if platform()!=JS then

end if

-- (note this gets overwritten by sorted set:)

else

printf(1,"working... %2d: %,d\r", {count+length(rares),rares[$]})

for n=0 to dis[level] do

end if

di[level] = n

end if

fnpr(level+1, nmr, di, dis, candidates, indices, fml, dmd)

else

end for

di = deep_copy(di)

end if

for n=0 to dis[level] do

end procedure

di[level] = n

fnpr(level+1, nmr, di, dis, candidates, indices, fml, dmd)

procedure fnmr(sequence terms, list, candidates, indices, fml, dmd, integer level)

end for

-- generate (n-r) candidates with a given number of digits.

end if

if level>length(list) then

end procedure

atom nmr = 0 -- (nmr == 'n - r')

for i=1 to length(terms) do

procedure fnmr(sequence terms, list, candidates, indices, fml, dmd, integer level)

nmr += terms[i][COEFF] * candidates[i]

-- generate (n-r) candidates with a given number of digits.

end for

if level>length(list) then

if nmr>0 and isSquare(nmr) then

atom nmr = 0 -- (nmr == 'n - r')

integer c = candidates[1]+1,

for i=1 to length(terms) do

l = length(fml[c])-1

nmr += terms[i][COEFF] * candidates[i]

sequence dis = {l}

end for

for i=2 to length(candidates) do

if nmr>0 and isSquare(nmr) then

c = candidates[i]+10

integer c = candidates[1]+1,

l = length(dmd[c])-1

l = length(fml[c])-1

dis = append(dis,l)

sequence dis = {l}

end for

for i=2 to length(candidates) do

if remainder(nd,2) then dis = append(dis,9) end if

c = candidates[i]+10

-- (above generates dis of eg {1,4,7,9} for nd=7, which as far

l = length(dmd[c])-1

-- as I (lightly) understand it scans for far fewer candidate

dis = append(dis,l)

-- pairs than a {9,9,9,9} would, or something like that.)

end for

sequence di = repeat(0,length(dis))

if remainder(nd,2) then dis = append(dis,9) end if

-- (di is the current "dis-scan", eg {0,0,0,0} to {1,4,7,9})

-- (above generates dis of eg {1,4,7,9} for nd=7, which as far

fnpr(1, nmr, di, dis, candidates, indices, fml, dmd)

-- as I (lightly) understand it scans for far fewer candidate

end if

-- pairs than a {9,9,9,9} would, or something like that.)

else

sequence di = repeat(0,length(dis))

for n=1 to length(list[level]) do

-- (di is the current "dis-scan", eg {0,0,0,0} to {1,4,7,9})

candidates[level] = list[level][n]

fnpr(1, nmr, di, dis, candidates, indices, fml, dmd)

fnmr(terms, list, candidates, indices, fml, dmd, level+1)

end if

end for

else

end if

candidates = deep_copy(candidates)

end procedure

for n=1 to length(list[level]) do

candidates[level] = list[level][n]

constant dl = tagset(9,-9), -- all differences (-9..+9 by 1)

fnmr(terms, list, candidates, indices, fml, dmd, level+1)

zl = tagset(0, 0), -- zero difference (0 only)

end for

el = tagset(8,-8, 2), -- even differences (-8 to +8 by 2)

end if

ol = tagset(9,-9, 2), -- odd differences (-9..+9 by 2)

end procedure

il = tagset(9, 0) -- all integers (0..9 by 1)

constant dl = tagset(9,-9), -- all differences (-9..+9 by 1)

procedure main()

zl = tagset(0, 0), -- zero difference (0 only)

atom start = time()

el = tagset(8,-8, 2), -- even differences (-8 to +8 by 2)

ol = tagset(9,-9, 2), -- odd differences (-9..+9 by 2)

-- terms of (n-r) expression for number of digits from 2 to maxdigits

il = tagset(9, 0) -- all integers (0..9 by 1)

sequence allTerms = {}

atom pow = 1

procedure main()

for r=2 to maxDigits do

atom start = time()

sequence terms = {}

pow *= 10

-- terms of (n-r) expression for number of digits from 2 to maxdigits

atom p1 = pow, p2 = 1

sequence allTerms = {}

integer tdxa = 0, tdxb = r-1

atom pow = 1

while tdxa < tdxb do

for r=2 to maxDigits do

terms = append(terms,{p1-p2, tdxa, tdxb}) -- {COEFF,TDXA,TDXB}

sequence terms = {}

p1 /= 10

pow *= 10

p2 *= 10

atom p1 = pow, p2 = 1

tdxa += 1

integer tdxa = 0, tdxb = r-1

tdxb -= 1

while tdxa < tdxb do

end while

terms = append(terms,{p1-p2, tdxa, tdxb}) -- {COEFF,TDXA,TDXB}

allTerms = append(allTerms,terms)

p1 /= 10

end for

p2 *= 10

--/*

tdxa += 1

--(This is what the above loop creates:)

tdxb -= 1

--pp(allTerms,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false,pp_IntFmt,"%d",pp_FltFmt,"%d",pp_Maxlen,148})

end while

{{{9,0,1}},

allTerms = append(allTerms,terms)

{{99,0,2}},

end for

{{999,0,3}, {90,1,2}},

--/*

{{9999,0,4}, {990,1,3}},

--(This is what the above loop creates:)

{{99999,0,5}, {9990,1,4}, {900,2,3}},

--pp(allTerms,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false,pp_IntFmt,"%d",pp_FltFmt,"%d",pp_Maxlen,148})

{{999999,0,6}, {99990,1,5}, {9900,2,4}},

<nowiki>{{</nowiki>{9,0,1<nowiki>}}</nowiki>,

{{9999999,0,7}, {999990,1,6}, {99900,2,5}, {9000,3,4}},

<nowiki>{{</nowiki>99,0,2<nowiki>}}</nowiki>,

{{99999999,0,8}, {9999990,1,7}, {999900,2,6}, {99000,3,5}},

<nowiki>{{</nowiki>999,0,3}, {90,1,2<nowiki>}}</nowiki>,

{{999999999,0,9}, {99999990,1,8}, {9999900,2,7}, {999000,3,6}, {90000,4,5}},

<nowiki>{{</nowiki>9999,0,4}, {990,1,3<nowiki>}}</nowiki>,

{{9999999999,0,10}, {999999990,1,9}, {99999900,2,8}, {9999000,3,7}, {990000,4,6}},

<nowiki>{{</nowiki>99999,0,5}, {9990,1,4}, {900,2,3<nowiki>}}</nowiki>,

{{99999999999,0,11}, {9999999990,1,10}, {999999900,2,9}, {99999000,3,8}, {9990000,4,7}, {900000,5,6}},

<nowiki>{{</nowiki>999999,0,6}, {99990,1,5}, {9900,2,4<nowiki>}}</nowiki>,

{{999999999999,0,12}, {99999999990,1,11}, {9999999900,2,10}, {999999000,3,9}, {99990000,4,8}, {9900000,5,7}},

<nowiki>{{</nowiki>9999999,0,7}, {999990,1,6}, {99900,2,5}, {9000,3,4<nowiki>}}</nowiki>,

{{9999999999999,0,13}, {999999999990,1,12}, {99999999900,2,11}, {9999999000,3,10}, {999990000,4,9}, {99900000,5,8}, {9000000,6,7}},

<nowiki>{{</nowiki>99999999,0,8}, {9999990,1,7}, {999900,2,6}, {99000,3,5<nowiki>}}</nowiki>,

{{99999999999999,0,14}, {9999999999990,1,13}, {999999999900,2,12}, {99999999000,3,11}, {9999990000,4,10}, {999900000,5,9}, {99000000,6,8}}}

<nowiki>{{</nowiki>999999999,0,9}, {99999990,1,8}, {9999900,2,7}, {999000,3,6}, {90000,4,5<nowiki>}}</nowiki>,

--*/

<nowiki>{{</nowiki>9999999999,0,10}, {999999990,1,9}, {99999900,2,8}, {9999000,3,7}, {990000,4,6<nowiki>}}</nowiki>,

<nowiki>{{</nowiki>99999999999,0,11}, {9999999990,1,10}, {999999900,2,9}, {99999000,3,8}, {9990000,4,7}, {900000,5,6<nowiki>}}</nowiki>,

-- map of first minus last digits for 'n' to pairs giving this value

<nowiki>{{</nowiki>999999999999,0,12}, {99999999990,1,11}, {9999999900,2,10}, {999999000,3,9}, {99990000,4,8}, {9900000,5,7<nowiki>}}</nowiki>,

sequence fml = repeat({},10) -- (aka 0..9)

<nowiki>{{</nowiki>9999999999999,0,13}, {999999999990,1,12}, {99999999900,2,11}, {9999999000,3,10}, {999990000,4,9}, {99900000,5,8}, {9000000,6,7<nowiki>}}</nowiki>,

-- (fml == 'first minus last')

<nowiki>{{</nowiki>99999999999999,0,14}, {9999999999990,1,13}, {999999999900,2,12}, {99999999000,3,11}, {9999990000,4,10}, {999900000,5,9}, {99000000,6,8<nowiki>}}</nowiki>}

fml[1] = {{2, 2}, {8, 8}}

--*/

fml[2] = {{6, 5}, {8, 7}}

fml[5] = {{4, 0}}

-- map of first minus last digits for 'n' to pairs giving this value

-- fml[6] = {{8, 3}} -- (um? - needs longer lists, & that append(lists[4],dl) below)

sequence fml = repeat({},10) -- (aka 0..9)

fml[7] = {{6, 0}, {8, 2}}

-- (fml == 'first minus last')

-- sequence lists = {{{0}},{{1}},{{4}},{{5}},{{6}}}

fml[1] = {{2, 2}, {8, 8}}

sequence lists = {{{0}},{{1}},{{4}},{{6}}}

fml[2] = {{6, 5}, {8, 7}}

-- map of other digit differences for 'n' to pairs giving this value

fml[5] = {{4, 0}}

sequence dmd = repeat({},19) -- (aka -9..+9, so add 10 when indexing dmd)

-- fml[6] = <nowiki>{{</nowiki>8, 3<nowiki>}}</nowiki> -- (um? - needs longer lists, & that append(lists[4],dl) below)

-- (dmd == 'digit minus digit')

fml[7] = {{6, 0}, {8, 2}}

for tens=0 to 9 do

-- sequence lists = <nowiki>{{</nowiki>{0<nowiki>}}</nowiki>,<nowiki>{{</nowiki>1<nowiki>}}</nowiki>,<nowiki>{{</nowiki>4<nowiki>}}</nowiki>,<nowiki>{{</nowiki>5<nowiki>}}</nowiki>,<nowiki>{{</nowiki>6<nowiki>}}</nowiki>}

integer d = tens+10

sequence lists = {{{0}},{{1}},{{4}},{{6}}}

for ones=0 to 9 do

-- map of other digit differences for 'n' to pairs giving this value

dmd[d] = append(dmd[d], {tens,ones})

sequence dmd = repeat({},19) -- (aka -9..+9, so add 10 when indexing dmd)

d -= 1

-- (dmd == 'digit minus digit')

end for

for tens=0 to 9 do

end for

integer d = tens+10

--/*

for ones=0 to 9 do

--(This is what the above loop creates:)

dmd[d] = append(dmd[d], {tens,ones})

--pp(dmd,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false})

d -= 1

{{{0,9}},

end for

{{0,8}, {1,9}},

end for

{{0,7}, {1,8}, {2,9}},

--/*

{{0,6}, {1,7}, {2,8}, {3,9}},

--(This is what the above loop creates:)

{{0,5}, {1,6}, {2,7}, {3,8}, {4,9}},

--pp(dmd,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false})

{{0,4}, {1,5}, {2,6}, {3,7}, {4,8}, {5,9}},

<nowiki>{{</nowiki>{0,9<nowiki>}}</nowiki>,

{{0,3}, {1,4}, {2,5}, {3,6}, {4,7}, {5,8}, {6,9}},

<nowiki>{{</nowiki>0,8}, {1,9<nowiki>}}</nowiki>,

{{0,2}, {1,3}, {2,4}, {3,5}, {4,6}, {5,7}, {6,8}, {7,9}},

~~{{0,1},~~ ~~{1,2},~~ {~~2,3},~~ {~~3,4}, {4,5}, {5,6}, {6~~,7}, {7,8}, {8,9}},

<nowiki>{{</nowiki>0,7}, {1,8}, {2,9<nowiki>}}</nowiki>,

~~{{0,0},~~ ~~{1,1},~~ {~~2,2},~~ {~~3,3}, {4,4}, {5,5}, {6~~,6}, {7,7}, {8,8}, {9,9}},

<nowiki>{{</nowiki>0,6}, {1,7}, {2,8}, {3,9<nowiki>}}</nowiki>,

~~{{1,0},~~ ~~{2,1},~~ {~~3,2},~~ {4,3}, {5,4}, {6,5}, {7,6}, {8,~~7}, {~~9,8}},

<nowiki>{{</nowiki>0,5}, {1,6}, {2,7}, {3,8}, {4,9<nowiki>}}</nowiki>,

{{2,0}, {3,1}, {4,2}, {5,3}, {6,4}, {7,5}, ~~{8,6}, {~~9,7}},

<nowiki>{{</nowiki>0,4}, {1,5}, {2,6}, {3,7}, {4,8}, {5,9<nowiki>}}</nowiki>,

{{3,0}, {4,1}, {5,2}, {6,3}, {7,4}, {8,5}, {9,6}},

<nowiki>{{</nowiki>0,3}, {1,4}, {2,5}, {3,6}, {4,7}, {5,8}, {6,9<nowiki>}}</nowiki>,

{{4,0}, {5,1}, {6,2}, {7,3}, {8,4}, {9,5}},

<nowiki>{{</nowiki>0,2}, {1,3}, {2,4}, {3,5}, {4,6}, {5,7}, {6,8}, {7,9<nowiki>}}</nowiki>,

{{5,0~~}, {6~~,1}, {7,2}, {8,3}, {9,4}},

<nowiki>{{</nowiki>0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8}, {8,9<nowiki>}}</nowiki>,

{{6,0}, {7,1}, {8,2}, {9,3}},

<nowiki>{{</nowiki>0,0}, {1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}, {7,7}, {8,8}, {9,9<nowiki>}}</nowiki>,

<nowiki>{{</nowiki>1,0}, {2,1}, {3,2}, {4,3}, {5,4}, {6,5}, {7,6}, {8,7}, {9,8<nowiki>}}</nowiki>,

{{7,0}, {8,1}, {9,2}},

<nowiki>{{</nowiki>2,0}, {3,1}, {4,2}, {5,3}, {6,4}, {7,5}, {8,6}, {9,7<nowiki>}}</nowiki>,

{{8,0}, {9,1}},

<nowiki>{{</nowiki>3,0}, {4,1}, {5,2}, {6,3}, {7,4}, {8,5}, {9,6<nowiki>}}</nowiki>,

{{9,0}}}

<nowiki>{{</nowiki>4,0}, {5,1}, {6,2}, {7,3}, {8,4}, {9,5<nowiki>}}</nowiki>,

--*/

<nowiki>{{</nowiki>5,0}, {6,1}, {7,2}, {8,3}, {9,4<nowiki>}}</nowiki>,

count = 0

<nowiki>{{</nowiki>6,0}, {7,1}, {8,2}, {9,3<nowiki>}}</nowiki>,

printf(1,"digits time nth rare numbers:\n")

<nowiki>{{</nowiki>7,0}, {8,1}, {9,2<nowiki>}}</nowiki>,

nd = 2

<nowiki>{{</nowiki>8,0}, {9,1<nowiki>}}</nowiki>,

while nd <= maxDigits do

<nowiki>{{</nowiki>9,0<nowiki>}}</nowiki>}

rares = {}

--*/

sequence terms = allTerms[nd-1]

count = 0

if nd=4 then

printf(1,"digits time nth rare numbers:\n")

lists[1] = append(lists[1],zl)

nd = 2

lists[2] = append(lists[2],ol)

while nd <= maxDigits do

lists[3] = append(lists[3],el)

rares = {}

-- lists[4] = append(lists[4],dl) -- if fml[6] = {{8, 3}}

sequence terms = allTerms[nd-1]

-- lists[5] = append(lists[5],ol) -- ""

if nd=4 then

lists[4] = append(lists[4],ol) -- else

lists[1] = append(lists[1],zl)

elsif length(terms)>length(lists[1]) then

lists[2] = append(lists[2],ol)

for i=1 to length(lists) do

lists[3] = append(lists[3],el)

lists[i] = append(lists[i],dl)

-- lists[4] = append(lists[4],dl) -- if fml[6] = <nowiki>{{</nowiki>8, 3<nowiki>}}</nowiki>

end for

-- lists[5] = append(lists[5],ol) -- ""

end if

-- lists[4] = append(lists[4],ol) -- else

sequence indices = {}

lists[4] = append(deep_copy(lists[4]),ol) -- else

for t=1 to length(terms) do

elsif length(terms)>length(lists[1]) then

sequence term = terms[t]

for i=1 to length(lists) do

-- (we may as well make this 1-based while here)

~~indices~~ = append(~~indices,{term~~[~~TDXA~~]+1,~~term[TDXB]+1}~~)

-- lists[i] = append(lists[i],dl)

lists[i] = append(deep_copy(lists[i]),dl)

end for

end for

for i=1 to length(lists) do

end if

sequence list = lists[i],

sequence indices = {}

candidates = repeat(0,length(list))

for t=1 to length(terms) do

fnmr(terms, list, candidates, indices, fml, dmd, 1)

sequence term = terms[t]

end for

-- (we may as well make this 1-based while here)

-- (re-)output partial results for this nd-set in sorted order:

indices = append(indices,{term[TDXA]+1,term[TDXB]+1})

rares = sort(rares)

end for

for i=1 to length(rares) do

for i=1 to length(lists) do

count += 1

sequence list = lists[i],

printf(1,"%12s %2d: %,19d \n", {"",count,rares[i]})

candidates = repeat(0,length(list))

end for

fnmr(terms, list, candidates, indices, fml, dmd, 1)

printf(1," %2d %5s\n", {nd, elapsed_short(time()-start)})

end for

nd += 1

-- (re-)output partial results for this nd-set in sorted order:

end while

-- rares = sort(rares)

end procedure

rares = sort(deep_copy(rares))

main()</lang>

for i=1 to length(rares) do

count += 1

printf(1,"%12s %2d: %,19d \n", {"",count,rares[i]})

end for

printf(1," %2d %5s\n", {nd, elapsed_short(time()-start)})

nd += 1

end while

end procedure

main()

<pre>