Challenge: Largest Reciprocal Cycle
Posted on: June 9, 2017 2:05:16 AMThis is another project euler challenge that states:
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.
This problem required me to do quite a bit of research on decimals with recurring cycles. I came across a wikipedia article that led me to Fermat's Little Theorem to get the number of digits in the cycle, aka, the period. From there, the problem was easy to solve.
Program.cs
using Common.Math;
using System;
namespace ProjectEuler_26
{
internal class Program
{
public static void Main(string[] args)
{
Tuple result = new Tuple(0, 0);
// start by getting primes up to 1000
var primes = Eratosthenes.GetPrimes(1000);
// loop backwards
for (int i = primes.Length - 1; i >= 0; i--)
{
int count;
// we know that the most a cyclical decimal will repeat is d-1
if ((count = GetCyclicalCount(primes[i])) == primes[i] - 1)
{
result = new Tuple(count, primes[i]);
break;
}
}
Console.WriteLine($"The value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part is {result.Item2} with {result.Item1} numbers in the cycle.");
}
private static int GetCyclicalCount(int prime)
{
int period = 1;
// using Fermat's Little Theorim you can get the count of numbers in the cycle referred to as a period
// Fermat's Little Theorim is defined as a^p=a%p
// where a is the number base and p is a prime of that number base
// this means that the count of cyclical numbers is the first modular power where the period test is not 1
while (ModularPow(10, period, prime) != 1)
{
period++;
}
return period;
}
private static int ModularPow(int @base, int exponent, int modulus)
{
if (modulus == 1) return 0;
int result = 1;
for (int i = 1; i <= exponent; i++)
{
result = (result * @base) % modulus;
}
return result;
}
}
}
The code is pretty well documented and explains what it's doing at just about every step. Enjoy!
Challenge: Lexicographic permutations
Posted on: October 19, 2016 2:12:46 AMThis challenge is to calculate the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Thinking back to my math classes in high school, I remembered that the maximum number of permutations possible for a given number can be calculated by n!. Knowing this, you can calculate any permutation value you want quickly without brute force. To figure out the first number, we need to calculate how many times we need to permutate 9!. 9! = 362880, so we know the first 362880 numbers start with 0, 362881 - 725760 start with 1, and 725761 - 1088640 start with 2. Because 1088640 is greater than the number we're attempting to look for, we know the first number in the answer has to be 2. Because we only know for sure that the 725761th permutation is 2013456789, we know we're 1000000 - 725761 or 274239 permutations away from the answer. We can keep using this method to narrow down to the final answer.
Program.cs
using Common.Math;
using System;
using System.Collections.Generic;
namespace ProjectEuler_24
{
internal class Program
{
private static void Main(string[] args)
{
List permNumbers = new List { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] answer = new int[10];
// the number of permutations remaining is 1 less than the number we are
// looking for because the first perumation is our starting point
int permutationsRemaining = 999999;
int answerIdx = 0;
for (int i = 1; i < 10; i++)
{
// because the most permutations possible is described as n!
// we want to figure out how many times we have to go through,
// this gives us the first number
int factorialVal = (10 - i).Factorial();
int x = permutationsRemaining / factorialVal;
// now we need to calculate how many permutations remain after
// we set the first number to continue narrowing down our calculation
permutationsRemaining = permutationsRemaining % factorialVal;
// set the answer then increment the index
answer[answerIdx++] = permNumbers[x];
// can't use the number again, remove it
permNumbers.RemoveAt(x);
// make sure we haven't already calculated the permuation value
// we're trying to get
if (permutationsRemaining == 0)
{
break;
}
}
Console.WriteLine($"The 1000000th lexicographic permutation is: {string.Join("", answer)}");
}
}
}
Factorial Code
public static int Factorial(this int num)
{
if (num < 0)
{
return 0;
}
int result = 1;
for (int i = 1; i <= num; i++)
{
result *= i;
}
return result;
}
The Factorial extension I've added to my common math library from the previous post. I've only posted the code to generate it rather than the full class since it's the only portion relevant.
Challenge: Non-abundant sums
Posted on: October 19, 2016 12:57:48 AMThis challenge wants you to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. An abundant number is described as the sum of the proper divisors are greater than the original number. For example, 12 is the smallest abundant number with it's divisors 1, 2, 3, 4, 6 summed together being 16. Where 12 is the smallest abundant number, 24 is would be the smallest abundant sum.
Program.cs
using Common.Math;
using System;
using System.Collections.Generic;
using System.Linq;
namespace ProjectEuler_23
{
internal class Program
{
private const int HighestNumNotAbundantSum = 28123;
private static bool IsAbundant(int i)
{
int[] factors = i.GetFactors().Distinct().ToArray();
int sum = factors.Sum() - i;
return sum > i;
}
private static void Main(string[] args)
{
int sum = 0;
bool[] isAbundantSum = new bool[HighestNumNotAbundantSum + 1];
List abundantNumbers = new List();
//12 is the lowest abundant number
for (int i = 12; i < HighestNumNotAbundantSum - 12; i++)
{
if (IsAbundant(i))
{
abundantNumbers.Add(i);
for (int x = 0; x < abundantNumbers.Count; x++)
{
int abundantSum = i + abundantNumbers[x];
if (abundantSum <= HighestNumNotAbundantSum)
{
isAbundantSum[abundantSum] = true;
}
}
}
}
for (int i = 1; i < isAbundantSum.Length; i++)
{
if (!isAbundantSum[i])
{
sum += i;
}
}
Console.WriteLine($"Sum of all numbers than can't be the sum of two abundant numbers: {sum}");
}
}
}
MathExtensions.cs
using System.Collections.Generic;
using System.Linq;
namespace Common.Math
{
public static class MathExtensions
{
public static int[] GetFactors(this int num)
{
List factors = new List { 1, num };
int root = (int)System.Math.Sqrt(num);
for (int i = 2; i <= root; i++)
{
if (num % i == 0)
{
factors.Add(i);
factors.Add(num / i);
}
}
return factors.OrderBy(x => x).ToArray();
}
}
}
This code is pretty straight forward, first we loop starting at 12 since it's the lowest known abundant number up to the highest non-abundant number known subtract 12. Then we determine if the number is abundant and store it. To use as few loops as possible, we then calculate out all the possible sums and store those values into a BitArray. Last, we loop through the BitArray and sum all the false values to get the answer.
As a note: I've moved the generating of factors code into a common library that I'm going to start referencing in projects that require it because it is a pretty common math function needed for these. This will likely be the last time I post the code for it, if you're following my posts, you should have this function working for your future projects as well.
Google Authenticator Service in .NET Core
Posted on: September 12, 2016 1:43:16 AMI'm in the process of converting my websites from ASP.NET 4 to .NET Core and one thing some of my sites use for added security is two factor authentication. .NET has a very nice built in handler for many types of authentication, including two factor; however, there was not any native support for Google Authenticator. Rather than try to switch my two factor to something already supported, I decided to take on the challenge of adding a new type. There is little to no documentation on how to do this as of my writing this, so it took a lot of research and digging into the source code of many .NET Core libraries. It was my goal to have the framework handle most of the leg work rather than do it myself.
GoogleAuthenticatorService.cs
public class GoogleAuthenticatorService<TUser> : TotpSecurityStampBasedTokenProvider<TUser> where TUser : class
{
private static readonly DateTime UNIX_EPOCH = new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc);
public override Task<bool> CanGenerateTwoFactorTokenAsync(UserManager<TUser> manager, TUser user)
{
return manager.GetTwoFactorEnabledAsync(user);
}
public string GenerateSecret()
{
byte[] buffer = new byte[9];
using (var rng = RandomNumberGenerator.Create())
{
rng.GetBytes(buffer);
}
return Convert.ToBase64String(buffer).Substring(0, 10).Replace('/', '0').Replace('+', '1');
}
public string GetCode(string secret, long counter)
{
return GeneratePassword(secret, counter);
}
public string GetCode(string secret)
{
return GetCode(secret, GetCurrentCounter());
}
public long GetCurrentCounter()
{
return GetCurrentCounter(DateTime.UtcNow, UNIX_EPOCH, 30);
}
public bool IsValid(string secret, string code, int checkAdjacentIntervals = 1)
{
if (code == GetCode(secret))
return true;
for (int i = 1; i <= checkAdjacentIntervals; i++)
{
if (code == GetCode(secret, GetCurrentCounter() + i))
return true;
if (code == GetCode(secret, GetCurrentCounter() - i))
return true;
}
return false;
}
public override async Task<bool> ValidateAsync(string purpose, string token, UserManager<TUser> manager, TUser user)
{
return IsValid(await manager.GetSecurityStampAsync(user), token);
}
private string GeneratePassword(string secret, long iterationNumber, int digits = 6)
{
byte[] counter = BitConverter.GetBytes(iterationNumber);
if (BitConverter.IsLittleEndian)
Array.Reverse(counter);
byte[] key = Encoding.ASCII.GetBytes(secret);
byte[] hash;
using (HMACSHA1 hmac = new HMACSHA1(key))
{
hash = hmac.ComputeHash(counter);
}
int offset = hash[hash.Length - 1] & 0xf;
int binary =
((hash[offset] & 0x7f) << 24)
| ((hash[offset + 1] & 0xff) << 16)
| ((hash[offset + 2] & 0xff) << 8)
| (hash[offset + 3] & 0xff);
int password = binary % (int)Math.Pow(10, digits);
return password.ToString(new string('0', digits));
}
private long GetCurrentCounter(DateTime now, DateTime epoch, int timeStep)
{
return (long)(now - epoch).TotalSeconds / timeStep;
}
}
The biggest thing I want to point out in this class is the base class TotpSecurityStampBasedTokenProvider<TUser> This is the class that allows us to register the class as a TokenProvider within .NET Core.
Startup.cs
public void ConfigureServices(IServiceCollection services)
{
services.AddSingleton(typeof(IConfigurationRoot), Configuration);
// Add framework services.
services.AddApplicationInsightsTelemetry(Configuration);
services.AddIdentity<ApplicationUser, IdentityRole>()
.AddEntityFrameworkStores<AuthDbContext>()
.AddTokenProvider<GoogleAuthenticatorService<ApplicationUser>>("Google");
services.AddMvc();
services.Configure<IdentityOptions>(options =>
{
options.Lockout.DefaultLockoutTimeSpan = TimeSpan.FromMinutes(10);
options.Lockout.MaxFailedAccessAttempts = 10;
});
services.Configure<CookieAuthenticationOptions>(options =>
{
options.LoginPath = new PathString("/Admin/Login");
});
}
You can see that we register the new TokenProvider and name it "Google".
AdminController.cs
[AllowAnonymous, HttpPost, ValidateAntiForgeryToken]
public async Task<IActionResult> Login(LoginViewModel loginModel, string returnUrl = null)
{
ViewData["ReturnUrl"] = returnUrl;
if (ModelState.IsValid)
{
var result = await _signInManager.PasswordSignInAsync(loginModel.Username, loginModel.Password, false, true);
if (result.Succeeded)
{
return RedirectToLocal(returnUrl);
}
else if (result.RequiresTwoFactor)
{
return View("TwoAuth");
}
else if (result.IsLockedOut)
{
return View("Login");
}
}
loginModel.Password = null;
return View(loginModel);
}
[AllowAnonymous]
public async Task<IActionResult> TwoAuth(string returnUrl = null)
{
ViewData["ReturnUrl"] = returnUrl;
var user = await _signInManager.GetTwoFactorAuthenticationUserAsync();
if (user == null)
{
return View("Login");
}
return View();
}
[AllowAnonymous, ValidateAntiForgeryToken, HttpPost]
public async Task<IActionResult> TwoAuth(string code, string returnUrl = null)
{
ViewData["ReturnUrl"] = returnUrl;
var user = await _signInManager.GetTwoFactorAuthenticationUserAsync();
if (user != null)
{
var result = await _signInManager.TwoFactorSignInAsync("Google", code, false, false);
if (result.Succeeded)
{
return RedirectToLocal(returnUrl);
}
else if (result.IsLockedOut)
{
return View("Login");
}
}
return View();
}
Here is a snippet of my AdminController that requires an authenticated user. As you can see, it checks if two factor auth is required. If it is, it tells it where to go to get the code. All of the details are taken care of using the built-in SignInManager.
Challenge: Amicable Numbers
Posted on: August 11, 2016 1:40:06 AMThis challenge describes an amicable number as:
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
The challenge is to get the sum of all the amicable numbers less than 10,000.
Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace ProjectEuler_21
{
internal class Program
{
private static int[] GetFactors(int num)
{
List factors = new List { 1, num };
int root = (int)Math.Sqrt(num);
for (int i = 2; i <= root; i++)
{
if (num % i == 0)
{
factors.Add(i);
factors.Add(num / i);
}
}
return factors.Distinct().OrderBy(i => i).ToArray();
}
private static int GetFactorsSum(int num)
{
int[] factors = GetFactors(num);
int sum = 0;
// don't include the actual num in the sum
for (int i = 0; i < factors.Length - 1; i++)
{
sum += factors[i];
}
return sum;
}
private static void Main(string[] args)
{
Dictionary cache = new Dictionary();
List amicableNumbers = new List();
int amicableCount = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 9999; i > 0; i--)
{
int factorSum = 0;
if (!cache.ContainsKey(i))
{
factorSum = GetFactorsSum(i);
cache[i] = factorSum;
}
else
{
factorSum = cache[i];
}
if (!cache.ContainsKey(factorSum))
{
cache[factorSum] = GetFactorsSum(factorSum);
}
if (cache[factorSum] == i && i != factorSum)
{
amicableCount++;
amicableNumbers.Add(i);
amicableNumbers.Add(factorSum);
}
}
sw.Stop();
amicableNumbers = amicableNumbers.Distinct().OrderBy(i => i).ToList();
Console.WriteLine("Number of amicable numbers under 10000: {0}\r\nSum of amicable numbers: {2}\r\nAmicable Numbers: {3}\r\nElapsed time: {1} ms", amicableCount, sw.ElapsedMilliseconds, amicableNumbers.Sum(), string.Join(", ", amicableNumbers));
}
}
}
From another challenge, we know how to easily and quickly calculate the factors of a number. So we can easily add to that logic by summing the factors to help us get an amicable number. I decided to cache the values, even though there really aren't many numbers we'd have to calculate twice. It ended up skimming off a couple of milliseconds.
Contact Me
Recent Blog Activity
Blog Archive