Recursive Numbering And Symmetric Numbers

[phillip1882]

so, i found this really cool idea over at xkcd. a recursive numbering system.

the rules are as follows.

if a number is composite, break it down into it's prime factors. if a number is prime, place < > around it and determine the n'th prime it is. if n is prime do again. if n is composite, break into prime factors.

then the first 20 numbers are

   1

<> 2

<<>> 3

<><> 4

<<<>>> 5

<><<>> 6

<<><>> 7

<><><> 8

<<>><<>> 9

<><<<>>> 10

<<<<>>>> 11

<><><<>> 12

<<><<>>> 13

<><<><>> 14

<<>><<<>>> 15

<><><><> 16

<<<><>>> 17

<><<>><<>> 18

<<><><>> 19

<><><<<>>> 20

a symmetric number then is a number, which using recursive numbering, can be written symmetric about the middle. the first few are...

 1 <> 2 <<>> 3 <><> 4 <<<>>> 5  <<><>> 7 <><><> 8 

<<>><<>> 9 <<<<>>>> 11 <><<>><> 12 <><><><> 16 <<<><>>> 17 

<<>><><<>> 18 <<><><>> 19 <><<<>>><> 20 <<<>><<>>> 23 <<<>>><<<>>> 25 

<<>><<>><<>> 27 <><<><>><> 28 <<<<<>>>>> 31 <><><><><> 32 <><<<><>>><>34

<><<>><<>><> 36 <<><<>><>> 37 <><<<<>>>><> 44 <<>><<<>>><<>> 45 <><><<>><><> 48

<<><>><<><>> 49 <><<<>>><<<>>><> 50 <<><><><>> 53 <<<<><>>>> 59 <<<>><><<>>> 61

<<>><<><>><<>> 63 <><><><><><> 64 <<<><><>>> 67 <><<<><>>><> 68 <<><<<>>><>> 71 

<<>><><><><<>> 72 <<<>>><<>><<<>>> 75 

Edited November 12, 2014 by phillip1882

[CraigD]

Cool! :thumbs_up

 

Here's a quick program in MUMPS execute code:

n (P) s P=$o(P(""),-1),Q=-1 s:P C=P(P) s:'P P=2,Q=0,C=0 f  s:'Q P(P)=C+1 q:'Q  s P=P+1 s Q=0 f  s Q=$o(P(Q)) q:'Q  q:P#Q=0  ;XBLDP: adds next prime to P(P)=N
s:D=1 D="" i D s E=0,F=$g(P(D)) s:F D="<"_F_">" i 'F f  s E=$o(P(E)) x:'E XBLDP s:'E E=P i D#E=0 s D="<"_P(E)_">"_$s(D-E:D\E,1:"") q  ;XMRNS(0,1)
n (R,XMRNS,XBLDP) s A=R x XMRNS(1,1) s R=A ;XMRNS(1): converts N into recursvise rep
f B=1:1 s C=$tr(A,"<>","  ") q:B>$l(C," ")  s D=$p(C," ",B) i $l(D) s X2=$l($p(C," ",1,B)),X1=X2-$l(D)+1 x XMRNS(0,1) s $e(A,X1,X2)=D ;XMRNS(1,1)

f A=1:1 s R=A x XMRNS(1) i $tr($re(R),"<>","><")=R w A," : ",R,! r R ;list symmetric numbers
1 :
2 : <>
3 : <<>>
4 : <><>
5 : <<<>>>
7 : <<><>>
8 : <><><>
9 : <<>><<>>
11 : <<<<>>>>
16 : <><><><>
17 : <<<><>>>
19 : <<><><>>
23 : <<<>><<>>>
25 : <<<>>><<<>>>
27 : <<>><<>><<>>
31 : <<<<<>>>>>
32 : <><><><><>
49 : <<><>><<><>>
53 : <<><><><>>
59 : <<<<><>>>>
64 : <><><><><><>
67 : <<<><><>>>
81 : <<>><<>><<>><<>>

Notice it doesn't get as many symmetric numbers as Phillip, because it breaks composite numbers into an ordered list of primes - for example, rather rather than the recursive number for 75 being the symmetric

<<<>>><<>><<<>>>

, my program gives

<<>><<<>>><<<>>>

 

The shows that, without this ordering rule ("canon"), recursive numbering isn't unique (or "canonical").

 

I wonder how the density of the symmetric numbers compare to that of the primes? Some composite numbers are symmetric, while some primes are not, so the answer to this question isn't obvious.

[phillip1882]

my code for producing all symmetric numbers between 1 and 1,000,000

import math

n = [False]*1000000

for i in range(1,1000):

   n[i*i] = True

p = 1

v = 2

while v < 1000000:

   k = 2

   if n[p]:

      for i in range(1,1000):

         if i*i*v < len(n):

            n[i*i*v] = True

   p += 1

   v += 1

   while k*k <= v:

      if v%k == 0:

         v += 1

         k = 1

      k += 1

f = open("symmetry.txt","w")

k = 1

total = 0

for i in range(1,len(n)):

   if n[i]:

      total += 1

      f.write(str(i)+" ")

      if k == 10:

         f.write("\n")

         k = 0

      k += 1

print(total)

gives 17,531 symmetric numbers between 1 and 1,000,000.

[CraigD]

my code for producing all symmetric numbers between 1 and 1,000,000

...

That’s a clever program, Phillip! :thumbs_up

 

I played with it enough to figure out how it works. Non-procedurally, it says:

S = N * N * V

Where

S is a symmetric number

N is a positive integer

V is 1 or a prime number that is also a symmetric number (for example, 13 prime but not symmetrical, so not in V).

 

Your program’s “if n[p]” condition takes advantage of the theorem that if a prime number P is symmetric, its position in the ordered list of primes C(P) must be a symmetric number, and C(P)<P, while its “while k*k <= v” is a simple prime number generator.

 

Notice it doesn't get as many symmetric numbers as Phillip, because it breaks composite numbers into an ordered list of primes - for example, rather rather than the recursive number for 75 being the symmetric

<<<>>><<>><<<>>>

, my program gives

<<>><<<>>><<<>>>

 

The shows that, without this ordering rule ("canon"), recursive numbering isn't unique (or "canonical").

I modified my program (at a cost of almost doubling its size, from 308 to 554 characters) to change the order of the prime factors to make them symmetrical when possible. Here it is:

n (P) s P=$o(P(""),-1),Q=-1 s:P C=P(P) s:'P P=2,Q=0,C=0 f  s:'Q P(P)=C+1 q:'Q  s P=P+1 s Q=0 f  s Q=$o(P(Q)) q:'Q  q:P#Q=0  ;XBLDP: adds next prime to P(P)=N
s:D=1 D="" i D x XMRNS(0,1,1) s D=G ;XMRNS(0,1)
x XMRNS(0,1,1,1),XMRNS(0,1,1,2),XMRNS(0,1,1,3) ;XMRNS(0,1,1)
k G s E=0,F=1,G=0 f  s:F E=$o(P(E)) x:'E XBLDP s:'E E=P s F=D#E i 'F s I=P(E),G(I)=1+$g(G(I)),G=G+1,G(I,G)="",D=D\E q:D<2  ;XMRNS(0,1,1,1)
k H s (E,G)=0 f  s E=$o(G(E)) q:'E  f  s G=$o(G(E,G)) q:'G  s H(G(E)+1#2,G)=E ;XMRNS(0,1,1,2)
s G="" f  s H=$Q(H) q:H=""  s I=@H,G=G_"<"_I_">" k @H s H=$Q(H) q:H=""  s I=@H,G="<"_I_">"_G k @H ;XMRNS(0,1,1,3)
n (P,R,XMRNS,XBLDP) s A=R x XMRNS(1,1) s R=A ;XMRNS(1): converts N into recurvise rep as described in http://www.scienceforums.com/topic/28018-recursive-numbering-and-symmetric-numbers/
f B=1:1 s C=$tr(A,"<>","  ") q:B>$l(C," ")  s D=$p(C," ",B) i $l(D) s X2=$l($p(C," ",1,B)),X1=X2-$l(D)+1 x XMRNS(0,1) s $e(A,X1,X2)=D ;XMRNS(1,1)

Even with the added cheat of preserving the list of primes it build as it factorizes numbers, using it to check a sequence of numbers is a much slower way to count symmetric numbers that Phillip’s program. In the time it took me to write this post, it only got as far as finding 2000 symmetric numbers in the first 35433 positive integers. Like most factorizing programs, it gets slower as the numbers increase, something like f(n) = O(n²). Edited November 28, 2014 by CraigD
Changed incorrect "20000" to "2000"

[phillip1882]

20,000? that's more than my program generates in 1,000,000. which number is symmetric that your program found that mine didn't?

[CraigD]

20,000? that's more than my program generates in 1,000,000. which number is symmetric that your program found that mine didn't?

Apologies. I wrote "finding 20000 symmetric numbers in the first 35433 positive integers" when I should have written "finding 2000 symmetric numbers in the first 35433 positive integers". I fixed my mistake. :(

 

Here's a list of where I found each 100th symetrical number:

100 311 <<><><><><><>>
200 908 <><<<><>><<><>>><>
300 1700 <<<>>><><<<><>>><><<<>>>
400 2645 <<<>><<>>><<<>>><<<>><<>>>
500 3761 <<<<>><<<<>>>><<>>>>
600 5047 <<><>><<<>><<>><<>>><<><>>
700 6476 <><<><><><><><><><>><>
800 8028 <<>><><<><><<>><><>><><<>>
900 9664 <><><><<<>><><><<>>><><><>
1000 11511 <<>><<<>><<<>><<>>><<>>><<>>
1100 13475 <<><>><<<>>><<<<>>>><<<>>><<><>>
1200 15331 <<><><><><<><>><><><><>>
1300 17629 <<<><>>><<<>><><<>>><<<><>>>
1400 19700 <<<>>><><<<>><<<>>><<>>><><<<>>>
1500 22079 <<<<>>><<>><<<<>>>><<>><<<>>>>
1600 24669 <<>><<<<>>><><><><><<<>>>><<>>
1700 27283 <<<>><><<<<>><<>>>><><<>>>
1800 29833 <<<>><<<>><><><><<>>><<>>>
1900 32957 <<><<<>><<<><>>><<>>><>>
2000 35443 <<<>><<>>><<<><><>>><<<>><<>>>

This vaguely resembles the distribution given by the prime number theorem, [math]\pi(x)\sim\frac{x}{\ln x}[/math].

[phillip1882]

seems much closer to me to be s(n) aprox. sqrt(n)*ln(n).

where s(n) is the number of symmetric numbers below n.

this gives

n   sqrt(n)*ln(n)

311 101

908 205

1700 306

2645 405

3761 504

5047 605

6476 706

8028 805

9664 902

11511 1003

13475 1103

15331 1193

17629 1298

19700 1387

22079 1486

24669 1588

27283 1687

29833 1779

32957 1888

35443 1972

Edited November 30, 2014 by phillip1882