Some number theory programs

Discuss your code, get questions answered

Some number theory programs

Postby d_motto » Tue Jul 03, 2012 2:44 pm

I have written some number theory programs. They are quite simple in most cases, but I have a few questions about them: Digits, PartConj, cool

The programs are as follows:

Factors

Code: Select all
≪ RECT @dup factors toElements 2. / { } 1. ROT START DUP 1. 4. ROLL START PICK3 + NEXT NIP NIP NEXT≫


This takes the result of factors (or FACTORS) and returns it as a string of factors, instead of pairs of factors and exponents.

UnitDivs

Code: Select all
≪ divs @dupdup reverse 2 ≪ gcd≫ DOLIST ≪ 1 ==≫ select≫


This returns the unitary divisors of a number: if a number n has a divisor d, and the GCD of d and n/d is 1, that is a unitary divisor.

Digits

Code: Select all
≪ split≫


This takes a number and splits it into an array of its component digits.

Question: What is the best way to handle something like -1.42e-13, which becomes [NaN 1 4 2 NaN NaN 13]? How do I get rid of the NaNs?

DblFact

Code: Select all
function (x) {     
  var d = 1;
  if (x < 2) return d;
  var i = x;
  while (i > 0) {
      d = d * i;
      i = i - 2;
  }
  return d;
}


I found an iOS calculator for free that had this function (press ! twice), and had to have it. It computes n*(n-2)*(n-4)...

Diffs

Code: Select all
≪ @dup tail 0 + - @dup size 1 - resize≫


Computes successive differences of a vector: start with a range of 1 to 10, square it, and get the successive differences of -3 -5 -7 -9 etc. to -19, run it again and the differences are all 2.

PartConj

Code: Select all
≪ @dup 'v' @var_store [] 'a' @var_store 1 at 1 - 0 @swap FOR x v ≪ x > ≫ map total a @swap + 'a' @var_store NEXT a≫


This computes the conjugate of a partition: if a partition is described by a Ferrers diagram:
11 = 5 3 1 1 1
XXXXX
XXX
X
X
X
The conjugate is as if you are reading down instead of across:
5 2 2 1 1

Like most of my code, this doesn't do any checking of the input.

Question: Why does the variable a stick around after the program has run. How do I use a local variable?

cool

Code: Select all
≪ 'age' @var_store "Nxt" age nextPrime @tag "Prv" age prevPrime @tag "Divs" age ndivs @tag "Phi" age phi @tag "Rdcl" age radical @tag "sigma" age 1 sigma @tag "Hex" age toHex @tag "Oct" age toOct @tag "Ulam" age Ulam @drop @tag age Factors≫


I wrote a function to figure out my age in days, and this function displays some cool things about the resulting number (like, with the factors, how old I would be if years were 253 days long or something like that.

Now, I rewrote this as

Code: Select all
≪ →n ≪ "Nxt" n nextPrime @tag "Prv" n prevPrime @tag "Divs" n ndivs @tag "Phi" n phi @tag "Rdcl" n radical @tag "sigma" n 1 sigma @tag "Hex" n toHex @tag "Oct" n toOct @tag "Ulam" n Ulam @drop @tag n Factors ≫ ≫


Question: why doesn't this work? I wanted to use a local variable n instead of one that hangs around after the program has run (age in the first example).

Dave Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Some number theory programs

Postby d_motto » Tue Jul 03, 2012 2:46 pm

Oops, Digits will return

[NaN 1 4 2 NaN NaN 1 3]

for that input, not

[NaN 1 4 2 NaN NaN 13]

I left out a space.

Dave Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Some number theory programs

Postby d_motto » Mon Jul 09, 2012 6:50 pm

Okay, I found the =a construct to create a local variable, and fixed my programs.

Here are a couple of other programs.

Derange computes the subfactorial; the number of permutations where every item is in a different place than the original order.

Code: Select all
≪ abs int factorial e / 0  round≫


This one needs work: Period is supposed to compute the length of the period of a reciprocal, enter then number and you get the period of the reciprocal; but it doesn't work for numbers like 6.

Code: Select all
≪ =n n @dup 1 - 1 @swap FOR x 10 x n modpow @dup 0 IF == THEN @drop "=terminates" @tag BREAK END IF 1 == THEN x "=period" @tag BREAK END NEXT≫


Question: why doesn't it work?

Dave Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Some number theory programs

Postby oliver » Sat Jul 14, 2012 1:49 am

Hi Dave,

I'm so sorry. I didn't notice these posts until just now. Didn't mean to ignore you and will come back with answers this weekend.

Congrats on all those great programs!

Oliver
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Some number theory programs

Postby oliver » Sat Jul 14, 2012 2:14 pm

Dave,

Ok. These are some nice programs! I especially like UnitDivs--clever and short.

General comment: you may wanna try using [ instructions ] (or { instructions }, which is the same) vs. ≪ instructions ≫.
This is usually (quite a bit) faster for a small number of instructions.

I'm glad you found the =name syntax to assign (and re-assign) a value to a local variable. Much better to use this than global vars.

This
Code: Select all
≪ →n ≪ ... ≫ ≫

didn't work, because you need a space character after the arrow.
I still recommend you use the =n syntax (with no space!). It's easier to type, read, and it's running faster, too. Plus, you save a set of pesky ≪ ≫.
Also, note that the classic syntax of re-assigning a local created with the arrow syntax requires you to use @var_store (STO). (Although, in ND1, you can actually mix syntaxes and simply re-assign with =n.)

Re your open question on Digits. I don't know. What you like to happen?
You can remove the NaNs like so
Code: Select all
≪ split [isInt] filter ≫

but I doubt you really want [1 4 2 1 3] to be your result vector.

There's no checking for NaNs in the code for split because it needed to be fast. I used it on a bunch of http://projecteuler.net problems. (Have you heard of/seen this site? If you like Number Theory, you may like these problems. If you do, you may wanna check out http://naivedesign.com/ND1/Project_Euler.html. Or don't look at it, to not have your fun spoiled...)

There's a bunch of things you could do with the JavaScript Date object. https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Date/ Figuring the number of days since you're born would be an easy thing to do, for example. How did you implement it? (EDIT: Oops. I *knew* there was a discussion about this but I forgot to look in Bugs for it... This http://forums.naivedesign.com/viewtopic.php?f=8&t=517, of course, is the answer to my question... :oops: )

The build-your-own-UI update to ND1 has a Birthday Info UI which allows you to pick a date and see what Wolfram Alpha has to say about that.

Cheers.

Oliver
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Some number theory programs

Postby d_motto » Thu Jul 26, 2012 8:42 pm

Thank you, Oliver. I have looked at the Project Euler website and the results you and others have provided. I am more interested in creating general-purpose functions than solving specific problems, but I had worked my way through a book called Puzzled Programmers by Microsoft Press, using ND1 and one of the many free BASIC interpreters to solve what I could. There are 15 puzzles and I did about 75% of them.

David Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am


Return to Programming

Who is online

Users browsing this forum: Google [Bot] and 1 guest

cron