a neat picture based on recursive number

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
phillip1882
Posts: 106
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

a neat picture based on recursive number

Postby phillip1882 » Mon Sep 03, 2018 11:17 pm UTC

https://ibb.co/kPRY2z
this picture represents the first 4000 numbers in recursive format.
<> 2
<<>> 3
<><>4
<<<>>> 5
and so on
the left arrow turns the turtle left 30 degrees then moves forward 5 and the right arrow rotate right 60 degrees and then move forward 5
heres the python code that produced it

Code: Select all

import turtle
recurse = [""]*1000000
recurse[2] = "<>"
n = 2
p = 1
while n < len(recurse):
   for v in range(2,int(len(recurse)/n)):
      if recurse[v] != "":
         recurse[v*n] = recurse[v] +recurse[n]
    
   n += 1
   while n<len(recurse) and recurse[n] != "":
      n += 1
   if n == len(recurse):
      break
   p += 1
   recurse[n] = "<" +recurse[p] +">"
turtle.screensize(7000,4500)
turtle.up()   
turtle.sety(-200)
turtle.down()
for i in range(2,len(recurse)):
   for j in range(0,len(recurse[i])):
      if recurse[i][j] == ">":
         turtle.right(60)
         turtle.forward(5)
      else:
         turtle.left(30)
         turtle.forward(5)
   print(recurse[i],i)
input()
good luck have fun

User avatar
Xanthir
My HERO!!!
Posts: 5311
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: a neat picture based on recursive number

Postby Xanthir » Wed Sep 05, 2018 5:55 am UTC

First, neat picture! It's always cool to see the kind of emergent patterns that come out of simple rules like this.

Second, the few numbers you provided give *no* clue as to the pattern you're following. I had to puzzle thru your Python to figure it out instead. From what I can tell, the pattern is:

1. The 1st pattern, P₁, is the empty string.
2. If n is the mth prime, then Pₙ = "<" + Pₘ + ">". (So, since 2 is the 1st prime, P₂ = <>, which is P₁ wrapped in angle brackets. 3 is the 2nd prime, so it's <<>>, P₂ wrapped. 5 is P₃ wrapped, 7 is P₄ wrapped, 11 is P₅ wrapped, etc.)
3. If n is composite, it can be divided into its smallest prime factor j and the rest of the number k. Pₙ is then Pₖ+Pⱼ. (So P₄ is P₂+P₂ <><>, P₁₂ is P₄+P₃ <><><<>>, P₁₀₀ is P₅₀+P₂, etc.)

Third, your use of single-letter variables and some slightly unidiomatic Python made it a bit hard to follow. I've rewritten it here to help myself understand:

Code: Select all

#!/usr/bin/env python2
def generatePatterns(limit):
   patterns = [""] * limit
   prime = 2
   primeCount = 1
   while prime < limit:
      # If N is the Mth prime, generate its pattern from the Mth pattern.
      patterns[prime] = "<" + patterns[primeCount] + ">"
      # Generate patterns for every possible multiple of prime
      # from the Prime'th pattern
      # and the Multiplier'th pattern
      for mult in xrange(2): # we won't use the whole range
         if mult*prime >= limit:
            break
         if patterns[multiplier]:
            patterns[multiplier*newPrime] = patterns[multiplier] + patterns[newPrime]
      # Now find the next prime.
      # Per Eratosthene's sieve, this is just the next unfilled value.
      while prime < limit and patterns[prime]:
         prime += 1
      primeCount += 1
   return patterns

def drawPatterns(patterns):
   import turtle
   turtle.screensize(7000,4500)
   turtle.up()
   turtle.sety(-200)
   turtle.down()
   for pattern in patterns:
      for command in pattern:
         if command == ">":
            turtle.right(60)
            turtle.forward(5)
         else:
            turtle.left(30)
            turtle.forward(5)
      print(pattern,i)

drawPatterns(generatePatterns(10**6))


I haven't run this, but I think it works? Is this code clear to you?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
phillip1882
Posts: 106
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a neat picture based on recursive number

Postby phillip1882 » Wed Sep 05, 2018 5:31 pm UTC

some small mistakes you made, i corrected them. mostly just using variables without declaring them

Code: Select all

def generatePatterns(limit):
   patterns = [""] * limit
   prime = 2
   primeCount = 1
   while prime < limit:
      # If N is the Mth prime, generate its pattern from the Mth pattern.
      patterns[prime] = "<" + patterns[primeCount] + ">"
      # Generate patterns for every possible multiple of prime
      # from the Prime'th pattern
      # and the Multiplier'th pattern
      for mult in range(2,len(patterns)): # we won't use the whole range
         if mult*prime >= limit:
            break
         if patterns[mult]:
            patterns[mult*prime] = patterns[mult] + patterns[prime]
      # Now find the next prime.
      # Per Eratosthene's sieve, this is just the next unfilled value.
      while prime < limit and patterns[prime]:
         prime += 1
      primeCount += 1
   return patterns


def drawPatterns(patterns):
   import turtle
   turtle.screensize(7000,4500)
   turtle.up()
   turtle.sety(-200)
   turtle.down()
   i = 0
   for pattern in patterns:
      for command in pattern:
         if command == ">":
            turtle.right(60)
            turtle.forward(5)
         else:
            turtle.left(30)
            turtle.forward(5)
      print(pattern,i)
      i+=1
drawPatterns(generatePatterns(10**6))
good luck have fun

FlatAssembler
Posts: 43
Joined: Fri Oct 27, 2017 7:42 pm UTC

Re: a neat picture based on recursive number

Postby FlatAssembler » Thu Sep 06, 2018 6:35 pm UTC

Didn't know Python supported turtle graphics, thanks for informing me.
Anyway, I've done a similar thing in JavaScript about a year ago. You can see it here. Though, admittedly, your looks even better.

User avatar
PM 2Ring
Posts: 3646
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: a neat picture based on recursive number

Postby PM 2Ring » Sat Sep 08, 2018 3:31 am UTC

Also see Dyck words.
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of square brackets [ and ]. The set of Dyck words forms Dyck language.

Dyck words and language are named after the mathematician Walther von Dyck. They have applications in the parsing of expressions that must have a correctly nested sequence of brackets, such as arithmetic or algebraic expressions.

User avatar
phlip
Restorer of Worlds
Posts: 7551
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: a neat picture based on recursive number

Postby phlip » Sat Sep 08, 2018 12:01 pm UTC

See also this thread over in Forum Games, which I suspect the OP is familiar with, but might not be familiar to others reading this thread...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Xanthir
My HERO!!!
Posts: 5311
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: a neat picture based on recursive number

Postby Xanthir » Wed Sep 12, 2018 4:16 pm UTC

Ah, indeed! I hadn't quite fully gathered the recursive nature there. So you're expressing a number solely by using the nth-prime() function, multiplication, and the number 1. For compactness, nth-prime(arg) is instead written as <arg>, multiplication is implicit from concatenation, and 1 can be omitted because it only and always appears at the deepest nesting of a <>. So 7 is nth-prime(4), aka nth-prime(2*2), aka nth-prime(nth-prime(1) * nth-prime(1)), and this can then be compacted to <<><>>.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
phillip1882
Posts: 106
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: a neat picture based on recursive number

Postby phillip1882 » Wed Sep 12, 2018 10:42 pm UTC

https://ibb.co/dxoNzp
another one for fun. its red for an even number of prime factors and blue for odd. its also toroidal, it wraps around the edges. also i made the right 45 rather than 60, and forward 3 rather than 5
this picture is roughly 1/4 the whole image.

Code: Select all

import time
import turtle

recurse = [""]*1000000
recurse[2] = "<>"
n = 2
p = 1
while n < len(recurse):
   for v in range(2,int(len(recurse)/n)):
      if recurse[v] != "":
         recurse[v*n] = recurse[v] +recurse[n]
    
   n += 1
   while n<len(recurse) and recurse[n] != "":
      n += 1
   if n == len(recurse):
      break
   p += 1
   recurse[n] = "<" +recurse[p] +">"
turtle.screensize(2000,2000)
turtle.up()   
turtle.sety(-200)
turtle.down()
turtle.speed(0)
turtle.hideturtle()
for i in range(2,len(recurse)):
   for j in range(0,len(recurse[i])):
      x,y = turtle.position()
      if x < -1000:
         turtle.up()
         turtle.setx(1000)
         turtle.down()
      elif x > 1000:
         turtle.up()
         turtle.setx(-1000)
         turtle.down()
      if y <-1000:
         turtle.up()
         turtle.sety(1000)
         turtle.down()
      elif y > 1000:
         turtle.up()
         turtle.sety(-1000)
         turtle.down()
      middle = 0
      total = 0
      for k in range(0,len(recurse[i])):
         if recurse[i][k] == "<":
            middle += 1
         else:
            middle -= 1
         if middle == 0:
            total +=1
      if total&1 == 0:
         turtle.color("red")
      else:
         turtle.color("blue")
      if recurse[i][j] == ">":
         turtle.right(45)
         turtle.forward(3)
      else:
         turtle.left(30)
         turtle.forward(3)
 
    
   print(recurse[i],i)
time.sleep(86400)
input()
good luck have fun


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests