Jan

21

A round-up of fun toys and tools

Filed Under teknolojia by | 2 Comments

Microsoft does a poor job of advertising new products, especially those in beta. Often this leads to the impression that Microsoft does not innovate. Here are some new products I’ve been playing with/using that are pretty cool.

  1. PowerPoint Plex (pptPlex) from Office Labs (http://www.officelabs.com/projects/pptPlex/Pages/default.aspx).If you’ve ever wished your slideshow could be something more than a linear series of slides, this is for you. You can can arrange your slides on a canvas, zoom in and out of slides and set your path for navigating through the slides. This means that you can have long code samples in your presentations and zoom into the sections you need as you need them. I can’t imagine going back to linear slides.
    An earlier version of Plex was used in this demo of Touch Wall.
  2. Script# (http://projects.nikhilk.net/ScriptSharp)This is the result of an independent project by Nikhil Kothari, an software architect in the .Net developer platform. Using the script# compiler, you can compile C# code into JavaScript (it does with C# what Google Web Toolkit does for Java). Here’s a blurb from Nikhil’s site.

    Script# brings productivity to Ajax and JavaScript development. Script# is a free tool that enables developers to author C# source code and subsequently compile it into regular script that works across all modern browsers, and in doing so, leverage the productivity and power of existing .NET tools as well as the Visual Studio IDE. Script# empowers you with a development methodology and approach that brings software engineering, long term maintainability and scalable development approaches for your Ajax applications, components and frameworks.

    With Script#, you can design your AJAX applications just as you would .Net applications – complete with object inheritance, namespaces, interfaces, event receivers, private methods etc. The JavaScript produced is browser independent, meaning that you get insulated from all the little browser quirks.

    You also get a lot of code re-use, just as with regular OOP. Script# provides its own base libraries for Ajax development, mirroring the libraries provided in the .Net platform. Alternatively, you can use base libraries from ASP.Net AJAX, or third party platforms like ExtJS(via Ext#). Script# produces a DLL with the JavaScript at compilation so your DLLs can be used in future projects as reference assemblies.

  3. Photosynth(http://photosynth.net/)This product from Microsoft Live Labs takes  set of photos and constructs a 3D model. The effects are pretty astounding.
  4. Songsmith(http://research.microsoft.com/en-us/um/redmond/projects/songsmith/index.html)This falls neatly into the toy category. This product from Microsoft Research allows you to hum or sing a tune and it generates an accompaniment. ArsTechnica had a really good article on this. There are some YouTube videos providing songsmith re-arrangements of classic tunes. My favorite is the remake of Roxanne by the Police.

Jan

16

Summing numbers that cannot be written as a sum of two abundant numbers

Filed Under hisabati, project euler by | Comments Off on Summing numbers that cannot be written as a sum of two abundant numbers

Problem 23 from Project Euler asks for the sum of numbers that cannot be written as the sum of two abundant numbers:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

When I read the problem, the requirements seemed to be pretty straight-forward. We need to find all the abundant numbers in the range so that we can determine all the numbers that are the sum of two abundant numbers. My first(naive) approach to this was terribly inefficient – it ran for hours and didn’t give the right answer. We cannot get around the need to determine the abundant numbers in range. However, we can reduce the search space when determining the numbers that are expressed as sums of two abundant numbers. To do this, we take advantage of some known properties:

  1. The upper bound for numbers that cannot be expressed as the sum of two numbers is actually 20161 not 28123 (as shown here).
  2. All even numbers greater than 48 can be written as the sum of two abundant numbers (also shown in the article here).

With these facts in mind, we are ready for the implementation. The first routine determines the abundant numbers in range.

  1: def abundant_nums_in_range(n):
  2:     abundant=[]
  3:     min_abundant_not_multiple_of_2_or_3 = 5391411025
  4:     for i in range(1,n):
  5:         if(i < min_abundant_not_multiple_of_2_or_3):
  6:             if(i % 2 != 0) and (i%3 != 0):
  7:                 continue
  8:         divisors = proper_divisors(i)
  9:         divisors_sum = 0
 10:         for d in divisors:
 11:             divisors_sum += d
 12:         if(divisors_sum > i):
 13:             abundant.append(i)
 14:     return abundant
 15:

The routine that determines proper divisors of a number tests divisors from 1 to the square-root of the number and extracts all divisors in pairs.

  1: def proper_divisors(n):
  2:     divisors =[]
  3:     maxValue = int(sqrt(n))+1
  4:     for i in range(1,maxValue):
  5:         if(n % i == 0):
  6:             if(i not in divisors):
  7:                 divisors.append(i)
  8:             quotient = n/i
  9:             if(quotient == n): continue
 10:             if(quotient not in divisors):
 11:                 divisors.append(quotient)
 12:     return divisors
 13:

The main routine for the solution is the method that determines all numbers in range that can be expressed as sum of two numbers. Since we know that all even numbers greater than 48 are in our target set, we only need to determine odd numbers in range. The only way to get an odd number by summing two numbers is to sum an even number with an odd.

  1: def abundant_pair_sums_in_range(n):
  2:     abundant_nums = abundant_nums_in_range(n)
  3:     even_abundants = []
  4:     odd_abundants = []
  5:     for a in abundant_nums:
  6:         if(a %2 == 0):
  7:             even_abundants.append(a)
  8:         else:
  9:             odd_abundants.append(a)
 10:     abundant_sum_nums = []
 11:     num_even_abundants = len(even_abundants)
 12:     num_odd_abundants = len(odd_abundants)
 13:     curr_num = 0
 14:     abundant_nums_filter = [0 for x in range(0,n)]
 15:     # all even numbers >48 are the sum of two abundants
 16:     for a in range(0,n):
 17:         if(a % 2 ==0):
 18:             if(a > 48):
 19:                 abundant_nums_filter[a] = 1
 20:             elif a in [24,30,32,36,38,40,42,44,48]:
 21:                 abundant_nums_filter[a] = 1
 22:     for i in range(0, num_even_abundants):
 23:         for j in range(0, num_odd_abundants):
 24:             curr_num = even_abundants[i] + odd_abundants[j]
 25:             if(curr_num < n):
 26:                 abundant_nums_filter[curr_num] = 1
 27:     for a in range(1,n):
 28:         if abundant_nums_filter[a] == 1 :
 29:             abundant_sum_nums.append(a)
 30:     return abundant_sum_nums
 31:

The last routine ties all operations together.

  1: def get_non_abundant_sums(n):
  2:     abundant_sums = abundant_pair_sums_in_range(n)
  3:     sum_all = sum([x for x in range(0,n)])
  4:     sum_abundants = sum(abundant_sums)
  5:     return (sum_all - sum_abundants)
  6:

Jan

2

Length of cycles in unit fractions

Filed Under hisabati, project euler by | Leave a Comment

Problem 26 of Project Euler asks us to find the length of cycles in unit fractions:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

The decimal representations of the fractions and therefore cycles can be discovered using long division. A python implementation of this would be:

  1: def unit_fraction_decimal_rep(n):
  2:     numerator, denominator = 1, n
  3:     fraction = []
  4:     remainders = {}
  5:     while True:
  6:         numerator *= 10
  7:         r = numerator % denominator
  8:         q = (numerator - r)/denominator
  9:         if(r == 0):
 10:             fraction.append(q)
 11:             break
 12:         if(r in remainders.values()):
 13:             foundCycle = False
 14:             for key,value in remainders.items():
 15:                 if(r == value) and (q == int(fraction[key])):
 16:                     # mark the cycle with parenthesis
 17:                     fraction.insert(key,"(")
 18:                     fraction.append(")")
 19:                     foundCycle = True
 20:                     break
 21:             if foundCycle:
 22:                 break
 23:         remainders[len(fraction)] = r
 24:         fraction.append(str(q))
 25:         numerator = r
 26:     return "0."+"".join(fraction)

To solve the problem posed, we could generate fractional representations of all integers from 1000 down and check for the longest cycles. However, looking at the algorithm above we can figure out how long a cycle will be without actually having to calculate it.

The terms in the decimal representation are determined by the remainder in each iteration of the loop starting on line 5 above. If one of the remainders is 0, then the fraction terminates. On the other hand, if we see a remainder that we have seen previously, then we have gotten to the end of a cycle. The maximum length of a cycle is n-1 since there are only n-1 possibilities for the remainder.

In each iteration of the loop on line 5, we multiply the numerator by 10. This establishes a relationship between 10 and n. We use a little algebra to explore the relationship.

  1. If the fraction terminates, then at some point we get a remainder of 0 meaning that n evenly divides a power of 10. Since 10 has only two divisors, 2 and 5, n evenly divides a power of 10 if and only if n = 2ax5b where a,b are non-negative integers (a or b may be 0 in which case n is either only divisible by 2 or by 5).
  2. The fraction will recur if n does not evenly divide any power of 10.
    • If n is has no factors in common with 10 (abbreviated as n is coprime with 10), the length of the recurring cycle is equal to the order of 10 in the group Zn (the multiplicative group of integers modulo n). If 10 has order d then 10d mod n = 1 and 1 becomes the first remainder repeated (since we start with numerator 1).
    • If n is not coprime with 10, there is no d for which 10d mod n = 1. In such cases n= 2ax5bxm where m is coprime with 10. So 1/n = 1/(2ax5b) x 1/m . The component 1/(2ax5b) will terminate so the cycle that results in 1/n is contributed by 1/m and the length of the cycle is equal to the order of 10 in Zm.

Applying this, we come up with the algorithm below:

  1: def recurring_cycle_length(n):
  2:     cycleLen = 0
  3:     #  remove powers of 2 and 5 in n
  4:     while (n % 2 == 0):
  5:         n /= 2
  6:     while (n % 5 == 0):
  7:         n /= 5
  8:     if n > 1:
  9:         a = 10 % n
 10:         cycleLen = 1
 11:         while a != 1:
 12:             a *= 10
 13:             a %= n
 14:             cycleLen += 1
 15:     return cycleLen

The longest cycle will be generated when 10 has a high order in Zn or Zm. So when searching for the longest cycle we start with the maximum value of n in the range and move down. If n is prime, the order of 10 in the Zn is either n-1 or a divisor of n-1. If we find a max value for the period which is equal to n-1, we have found the longest cycle.

  1: def max_len_recurring_cycle_in_range(n):
  2:     # iterate from the max num down
  3:     maxCycleLen = 0
  4:     maxCycleLenGenerator = n
  5:     for i in range(n, 1, -1):
  6:         currLen = recurring_cycle_length(i)
  7:         if(currLen > maxCycleLen):
  8:             maxCycleLen = currLen
  9:             maxCycleLenGenerator = i
 10:         if(currLen == i-1):
 11:             break
 12:     return maxCycleLenGenerator, maxCycleLen