I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Magic constant

From Rosetta Code
Magic constant is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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


AWK[edit]

 
# syntax: GAWK -f MAGIC_CONSTANT.AWK
# converted from FreeBASIC
BEGIN {
printf("The first 20 magic constants are:")
for (i=1; i<=20; i++) {
printf(" %d",a(i))
}
printf("\n")
printf("The 1,000th magic constant is: %d\n",a(1000))
for (i=1; i<=20; i++) {
printf("10^%02d: %8d\n",i,inv_a(10^i))
}
exit(0)
}
function a(n) {
n += 2
return(n*(n^2+1)/2)
}
function inv_a(x, k) {
while (k*(k^2+1)/2+2 < x) {
k++
}
return(k)
}
 
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^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

Basic[edit]

FreeBASIC[edit]

 
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
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[edit]

$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
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[edit]

Works with: Factor version 0.99 2021-06-02
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
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[edit]

Uses the inverse of the magic constant function for the last part of the task.

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
 
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[edit]

#!/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;
}
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[edit]

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

Prolog[edit]

Minimalistic, efficient approach

 
m(X,Y):- Y is X*(X*X+1)/2.
 
l(L,R,T,X):- L > R -> X is L; M is div(L+R,2), m(M,F),
(T < F -> R_ is M-1, l(L,R_,T,X); L_ is M+1, l(L_,R,T,X)).
l(B,X):- l(1,B,B,X).
 
task:-
write("First 20 magic constants are:"), forall(between(3,22,N), (m(N,X), format(" ~d",X))), nl,
write("The 1000th magic constant is:"), forall(m(1002,X), format(" ~d",X)), nl,
forall(between(1,20,N), (l(10**N,X), format("10^~d:\t~d\n",[N,X]))).
 
Output:
?- task. 
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 1000th 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
true.

Raku[edit]

use Lingua::EN::Numbers:ver<2.8+>;
 
my @magic-constants = lazy (3..).hyper.map: { (1 + .²) * $_ / 2 };
 
put "First 20 magic constants: ", @magic-constants[^20]».&comma;
say "1000th magic constant: ", @magic-constants[999].&comma;
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 ) }
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[edit]

Library: Wren-seq
Library: Wren-fmt
Library: Wren-big

This uses Julia's approach for the final parts.

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)
}
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[edit]

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.

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.;
];
]
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