Egyptian Fractions

Originally posted by iamatiger
Rounding to nearest still wins when the denominator of the fraction to be decomposed ranges from 2..1000

on average to nearest needs 3.956 fractions, but rounding up needs 4.213 fractions

The smallest term in rounding to nearest is at 317/739 and is:
1/915546455684058748900662753016244979642885301214026384244483872977
531860755467415594381393201149 ...[text shortened]... 221462278567965155036846552482106
2859837409907538269572622296774545103747438431266995525592705

FIX'D:

The smallest term in rounding up is at 36/457 and is:
1/839018826833450186636781520007011999269820404906753180244759299287
83737889539760561326146999562649871928983511239253043084051410214699
86256665947569952734180156000234940492081088941857817740026830632042
52356172520941088783702738286944210460710059319691268110283467445381
02665362859976568473910538864231004478584490215707691900373523154378
17850733931761441676882524465414164664186084654585029979714254283427
69433127784560570193376772878336217849260872114137931351960543608384
24400950566425317387570523488957085392410564019361930133277698968824
85550270543952379075819512618682808991505743601648001879641672743230
78311078867593844043149124596271281252530924719121766925749760855109
10006673184147826281268664269339589622998374522627779305582060905834
82691521900836957046857696220116551591742723266473426955898181271263
03038171968768650476413027459205291075571637957597356820188031655122
74974365230126839454212397089242294433585791764163604189219254713517
81536020388776776143582815811036855260413298414968634103058882552344
95015115912388514981113593387572720476744188169200130515719608747338
81013672826778401335239691097990454591345853624332731197780512641006
55769612376408248521143288840865815420914926003128384256669276276742
27053793897767395465326589843035773944346372949759909905561209334216
84715815664488428130051269991053009287091906187661577070851924381867
63662454774620422942676746779547837269903493861174680719328740210237
14524610740225814235147693954027910741673103980749749728106483987721
60273867317300936280233709290884779749947589534711288933950292840780
80586702977221756866386787887386898039455740028056772504632864793636
70076942509109589495377221095405979217163821481666646160815221224686
56253053611661364530533592281952403782987896151817017796876836485339
90573577721416556223812801969086370315564364614042859304264369836581
06288733881761514992109680298995922754466040011586713812553117621857
10951725894384600417943252113184415624242835127018880391955439862008
46685140545044140622760122924973752382108865950062494534604147901476
11422121782194848803348777061816460876697945418158442269512987729152
44194032646663161042490615823728821870644796311301923955788548664731
40853576518952261173647603153943546245479192091385391808078296725459
24239541758108877100331729470119526373928796447673951888289511964811
PLEASE 6330253698211566 HELP 959345571034299210633879650467150701029
1681197655258446415398121427762259730 ME 811344932046234168305520057
6571910241686615924531368198770946893858410 I 0583482219856031514281
53382461711196734214085852523778422630907646235900 HAVE 752317571022
131569421231196329080023952364788544301495422061066036911772385739 O
BSESSIVE 65999766550383244452971354428695554 COMPULSIVE 831016616883
78890461490612964610594322386216021797248095100247721274970802584016
94929 DISORDER 97310518483221462278567965155036846552482106285983740
9907538269572622296774545103747438431266995525592705

Thanks swiss, here's the perl program that does it by the way:
The winiking smiley is a semicolon and a bracket of course.

use bigint;
use Math::BigInt;

sub divide {
my ($num, $div, $roundir) = @_;
my $ans_sign;
if ($num < 0) {
if ($div < 0) {
$ans_sign = 1;
}else{
$ans_sign = -1;
}
}else{
if ($div < 0) {
$ans_sign = -1;
}else{
$ans_sign = 1;
}
}
my $numcopy = Math::BigInt->new($num);
my $divcopy = Math::BigInt->new($div);
$numcopy->babs();
$divcopy->babs();
#stop destructive division etc

my ($quo, $rem) = $numcopy->bdiv($divcopy);
if ($roundir eq 'up'😉 {
if ($rem != 0) {
$quo += 1;
}
}else{
my $half = $div/2;
if ($rem > $half) {
$quo += 1;
}
}
return $quo*$ans_sign;
}

my %totals;
my $num_done;

my %max = ('max' => 0, 'to nearest' => 0);
my %max_loc;
open my $outfile_up, ">", "egypt_fracts_up.csv";
open my $outfile_near, ">", "egypt_fracts_near.csv";
my %outfiles = ('up' => $outfile_up, 'to nearest' => $outfile_near);
foreach my $outfile ($outfile_up, $outfile_near) {
print $outfile "enumerator,denominator,fractions...\n";
}

foreach my $denom (2..1000) {
foreach my $enum (1..$denom-1) {
$num_done++;
foreach my $roundir ('up','to nearest'😉 {
my @denoms;
my $rem_enum = Math::BigInt->new($enum);
my $rem_denom = Math::BigInt->new($denom);
while ($rem_enum != 0) {
my $egypt_denom = divide($rem_denom,$rem_enum,$roundir);
my $abs_denom = Math::BigInt->new($egypt_denom);
$abs_denom->babs();
if ($abs_denom > $max{$roundir}) {
$max{$roundir} = $abs_denom;
$max_loc{$roundir} = "$enum/$denom";
}
push @denoms, "'".$egypt_denom;
$rem_enum = $rem_enum*$egypt_denom - $rem_denom;
$rem_denom = $egypt_denom*$rem_denom;
}
my $outfile = $outfiles{$roundir};
print $outfile join(',',($enum,$denom,@denoms,"\n"😉);
$totals{$roundir} += scalar(@denoms);
}
}
}

foreach my $roundir ('up','to nearest'😉 {
my $av_num = $totals{$roundir} / $num_done;
print "Rounding $roundir gave $av_num fractions on average!\n";
print "The largest number for rounding $roundir was at".$max_loc{$roundir}."with:\n".$max{$roundir}."\n";
}