Magic constant
A magic square is a square grid containing consecutive integers from 1 to N², arranged so that every row, column and diagonal adds up to the same number. That number is a constant. There is no way to create a valid N x N magic square that does not sum to the associated constant.
- EG
A 3 x 3 magic square always sums to 15.
┌───┬───┬───┐
│ 2 │ 7 │ 6 │
├───┼───┼───┤
│ 9 │ 5 │ 1 │
├───┼───┼───┤
│ 4 │ 3 │ 8 │
└───┴───┴───┘
A 4 x 4 magic square always sums to 34.
Traditionally, the sequence leaves off terms for n = 0 and n = 1 as the magic squares of order 0 and 1 are trivial; and a term for n = 2 because it is impossible to form a magic square of order 2.
- Task
- Starting at order 3, show the first 20 magic constants.
- Show the 1000th magic constant. (Order 1003)
- Find and show the order of the smallest N x N magic square whose constant is greater than 10¹ through 10¹⁰.
- Stretch
- Find and show the order of the smallest N x N magic square whose constant is greater than 10¹¹ through 10²⁰.
- See also
- Wikipedia: Magic constant
- OEIS: A006003 (Similar sequence, though it includes terms for 0, 1 & 2.)
Basic
FreeBASIC
<lang freebasic> function a(byval n as uinteger) as ulongint
n+=2 return n*(n^2 + 1)/2
end function
function inv_a(x as double) as ulongint
dim as ulongint k = 0
while k*(k^2+1)/2+2 < x
k+=1
wend
return k
end function
dim as ulongint n print "The first 20 magic constants are ": for n = 1 to 20
print a(n);" ";
next n print print "The 1,000th magic constant is ";a(1000)
for e as uinteger = 1 to 20
print using "10^##: #########";e;inv_a(10^cast(double,e))
next e</lang>
- Output:
The first 20 magic constants are 15 34 65 111 175 260 369 505 671 870 1105 1379 1695 2056 2465 2925 3439 4010 4641 5335 The 1,000th magic constant is 503006505 10^ 1: 3 10^ 2: 6 10^ 3: 13 10^ 4: 28 10^ 5: 59 10^ 6: 126 10^ 7: 272 10^ 8: 585 10^ 9: 1260 10^10: 2715 10^11: 5849 10^12: 12600 10^13: 27145 10^14: 58481 10^15: 125993 10^16: 271442 10^17: 584804 10^18: 1259922 10^19: 2714418 10^20: 5848036
QB64
<lang qbasic>$NOPREFIX
DIM order AS INTEGER DIM target AS INTEGER64
PRINT "First 20 magic constants:" FOR i = 3 TO 22
PRINT USING "####, "; MagicSum(i); IF i MOD 5 = 2 THEN PRINT
NEXT i PRINT PRINT USING "1000th magic constant: ##########,"; MagicSum(1002) PRINT PRINT "Smallest order magic square with a constant greater than:" FOR i = 1 TO 13 ' 64-bit integers can take us no further, unsigned or not
target = 10 ^ i
DO
order = order + 1
LOOP UNTIL MagicSum(order) > target
PRINT USING "10^**: #####,"; i; order
order = order * 2 - 1
NEXT i
FUNCTION MagicSum&& (n AS INTEGER)
MagicSum&& = (n * n + 1) / 2 * n
END FUNCTION</lang>
- Output:
First 20 magic constants: 15 34 65 111 175 260 369 505 671 870 1,105 1,379 1,695 2,056 2,465 2,925 3,439 4,010 4,641 5,335 1000th magic constant: 503,006,505 Smallest order magic square with a constant greater than: 10^*1: 3 10^*2: 6 10^*3: 13 10^*4: 28 10^*5: 59 10^*6: 126 10^*7: 272 10^*8: 585 10^*9: 1,260 10^10: 2,715 10^11: 5,849 10^12: 12,600 10^13: 27,145
Factor
<lang factor>USING: formatting io kernel math math.functions.integer-logs math.ranges prettyprint sequences ;
- magic ( m -- n ) dup sq 1 + 2 / * ;
"First 20 magic constants:" print 3 22 [a,b] [ bl ] [ magic pprint ] interleave nl nl "1000th magic constant: " write 1002 magic . nl "Smallest order magic square with a constant greater than:" print 1 0 20 [
[ 10 * ] dip [ dup magic pick < ] [ 1 + ] while over integer-log10 over "10^%02d: %d\n" printf dup + 1 -
] times 2drop</lang>
- Output:
First 20 magic constants: 15 34 65 111 175 260 369 505 671 870 1105 1379 1695 2056 2465 2925 3439 4010 4641 5335 1000th magic constant: 503006505 Smallest order magic square with a constant greater than: 10^01: 3 10^02: 6 10^03: 13 10^04: 28 10^05: 59 10^06: 126 10^07: 272 10^08: 585 10^09: 1260 10^10: 2715 10^11: 5849 10^12: 12600 10^13: 27145 10^14: 58481 10^15: 125993 10^16: 271442 10^17: 584804 10^18: 1259922 10^19: 2714418 10^20: 5848036
Julia
Uses the inverse of the magic constant function for the last part of the task. <lang julia>using Lazy
magic(x) = (1 + x^2) * x ÷ 2 magics = @>> Lazy.range() map(magic) filter(x -> x > 10) # first 2 values are filtered out println("First 20 magic constants: ", Int.(take(20, magics))) println("Thousandth magic constant is: ", collect(take(1000, magics))[end])
println("Smallest magic square with constant greater than:") for expo in 1:20
goal = big"10"^expo
ordr = Int(floor((2 * goal)^(1/3))) + 1
println("10^", string(expo, pad=2), " ", ordr)
end
</lang>
- Output:
First 20 magic constants: [15, 34, 65, 111, 175, 260, 369, 505, 671, 870, 1105, 1379, 1695, 2056, 2465, 2925, 3439, 4010, 4641, 5335] Thousandth magic constant is: 503006505 Smallest magic square with constant greater than: 10^01 3 10^02 6 10^03 13 10^04 28 10^05 59 10^06 126 10^07 272 10^08 585 10^09 1260 10^10 2715 10^11 5849 10^12 12600 10^13 27145 10^14 58481 10^15 125993 10^16 271442 10^17 584804 10^18 1259922 10^19 2714418 10^20 5848036
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Magic_constant use warnings;
my @twenty = map $_ * ( $_ ** 2 + 1 ) / 2, 3 .. 22; print "first twenty: @twenty\n\n" =~ s/.{50}\K /\n/gr;
my $thousandth = 1002 * ( 1002 ** 2 + 1 ) / 2; print "thousandth: $thousandth\n\n";
print "10**N order\n"; for my $i ( 1 .. 20 )
{
printf "%3d %9d\n", $i, (10 ** $i * 2) ** ( 1 / 3 ) + 1;
}</lang>
- Output:
first twenty: 15 34 65 111 175 260 369 505 671 870 1105 1379 1695 2056 2465 2925 3439 4010 4641 5335 thousandth: 503006505 10**N order 1 3 2 6 3 13 4 28 5 59 6 126 7 272 8 585 9 1260 10 2715 11 5849 12 12600 13 27145 14 58481 15 125993 16 271442 17 584804 18 1259922 19 2714418 20 5848036
Phix
with javascript_semantics function magic(integer nth) integer order = nth+2 return (order*order+1)/2 * order end function printf(1,"First 20 magic constants: %V\n",{apply(tagset(20),magic)}) printf(1,"1000th magic constant: %,d\n",{magic(1000)}) include mpfr.e mpz {goal, order} = mpz_inits(2) for i=1 to 20 do mpz_ui_pow_ui(goal,10,i) mpz_mul_si(order,goal,2) mpz_nthroot(order,order,3) mpz_add_si(order,order,1) printf(1,"1e%d: %s\n",{i,mpz_get_str(order,10,true)}) end for
- Output:
First 20 magic constants: {15,34,65,111,175,260,369,505,671,870,1105,1379,1695,2056,2465,2925,3439,4010,4641,5335}
1000th magic constant: 503,006,505
1e1: 3
1e2: 6
1e3: 13
1e4: 28
1e5: 59
1e6: 126
1e7: 272
1e8: 585
1e9: 1,260
1e10: 2,715
1e11: 5,849
1e12: 12,600
1e13: 27,145
1e14: 58,481
1e15: 125,993
1e16: 271,442
1e17: 584,804
1e18: 1,259,922
1e19: 2,714,418
1e20: 5,848,036
Raku
<lang perl6>use Lingua::EN::Numbers:ver<2.8+>;
my @magic-constants = lazy (3..∞).hyper.map: { (1 + .²) * $_ / 2 };
put "First 20 magic constants: ", @magic-constants[^20]»., say "1000th magic constant: ", @magic-constants[999]., say "\nSmallest order magic square with a constant greater than:";
(1..20).map: -> $p {printf "10%-2s: %s\n", $p.&super, comma 3 + @magic-constants.first( * > exp($p, 10), :k ) }</lang>
- Output:
First 20 magic constants: 15 34 65 111 175 260 369 505 671 870 1,105 1,379 1,695 2,056 2,465 2,925 3,439 4,010 4,641 5,335 1000th magic constant: 503,006,505 Smallest order magic square with a constant greater than: 10¹ : 3 10² : 6 10³ : 13 10⁴ : 28 10⁵ : 59 10⁶ : 126 10⁷ : 272 10⁸ : 585 10⁹ : 1,260 10¹⁰: 2,715 10¹¹: 5,849 10¹²: 12,600 10¹³: 27,145 10¹⁴: 58,481 10¹⁵: 125,993 10¹⁶: 271,442 10¹⁷: 584,804 10¹⁸: 1,259,922 10¹⁹: 2,714,418 10²⁰: 5,848,036
Wren
This uses Julia's approach for the final parts. <lang ecmascript>import "./seq" for Lst import "./fmt" for Fmt import "./big" for BigInt
var magicConstant = Fn.new { |n| (n*n + 1) * n / 2 }
var ss = ["\u2070", "\u00b9", "\u00b2", "\u00b3", "\u2074",
"\u2075", "\u2076", "\u2077", "\u2078", "\u2079"]
var superscript = Fn.new { |n| (n < 10) ? ss[n] : (n < 20) ? ss[1] + ss[n - 10] : ss[2] + ss[0] }
System.print("First 20 magic constants:") var mc20 = (3..22).map { |n| magicConstant.call(n) }.toList for (chunk in Lst.chunks(mc20, 10)) Fmt.print("$5d", chunk)
Fmt.print("\n1,000th magic constant: $,d", magicConstant.call(1002))
System.print("\nSmallest order magic square with a constant greater than:") for (i in 1..20) {
var goal = BigInt.ten.pow(i)
var order = (goal * 2).icbrt + 1
Fmt.print("10$-2s : $,9i", superscript.call(i), order)
}</lang>
- Output:
First 20 magic constants: 15 34 65 111 175 260 369 505 671 870 1105 1379 1695 2056 2465 2925 3439 4010 4641 5335 1,000th magic constant: 503,006,505 Smallest order magic square with a constant greater than: 10¹ : 3 10² : 6 10³ : 13 10⁴ : 28 10⁵ : 59 10⁶ : 126 10⁷ : 272 10⁸ : 585 10⁹ : 1,260 10¹⁰ : 2,715 10¹¹ : 5,849 10¹² : 12,600 10¹³ : 27,145 10¹⁴ : 58,481 10¹⁵ : 125,993 10¹⁶ : 271,442 10¹⁷ : 584,804 10¹⁸ : 1,259,922 10¹⁹ : 2,714,418 10²⁰ : 5,848,036
XPL0
A magic square of side N contains N^2 items. The sum of a sequence 1..N^2 is given by: Sum = (N^2+1) * N^2 / 2. A grid row adds to the magic constant, and N rows add to the Sum. Thus the magic constant = Sum/N = (N^3+N)/2. <lang XPL0>int N, X; real M, Thresh, MC; [Text(0, "First 20 magic constants:^M^J"); for N:= 3 to 20+3-1 do
[IntOut(0, (N*N*N+N)/2); ChOut(0, ^ )];
CrLf(0); Text(0, "1000th magic constant: "); N:= 1000+3-1; IntOut(0, (N*N*N+N)/2); CrLf(0); Text(0, "Smallest order magic square with a constant greater than:^M^J"); Thresh:= 10.; M:= 3.; Format(1, 0); for X:= 1 to 10 do
[repeat MC:= (M*M*M+M)/2.;
M:= M+1.;
until MC > Thresh;
Text(0, "10^^");
if X < 10 then ChOut(0, ^0);
IntOut(0, X);
Text(0, ": ");
RlOut(0, M-1.);
CrLf(0);
Thresh:= Thresh*10.;
];
]</lang>
- Output:
First 20 magic constants: 15 34 65 111 175 260 369 505 671 870 1105 1379 1695 2056 2465 2925 3439 4010 4641 5335 1000th magic constant: 503006505 Smallest order magic square with a constant greater than: 10^01: 3 10^02: 6 10^03: 13 10^04: 28 10^05: 59 10^06: 126 10^07: 272 10^08: 585 10^09: 1260 10^10: 2715