Appellant Donald Ben Bartsma pleaded guilty to one count of possession of a firearm by a convicted felon in violation of 18 U.S.C. § 922(g)(1) and was sentenced to fifty-eight months imprisonment. In arriving at the final sentence, the district court departed upward from the otherwise applicable Guideline range pursuant to United States Sentencing Guideline 4A1.3. The district court also imposed a special condition of supervised release requiring Mr. Bartsma to register as a "sex offender" in any state in which he resides after his release from prison. Mr. Bartsma now appeals, challenging the district court's upward departure, the special condition of supervised release, and also claiming he was entitled to presentence notice of the court's intention to consider imposing sex offender registration as a special condition of supervised release. We exercise jurisdiction pursuant to 28 U.S.C. § 1291 and 18 U.S.C. § 3742. We affirm in part, reverse in part, and remand for resentencing.

Mr. Bartsma's appeal focuses exclusively on the propriety of his sentence and conditional release. As such, we only briefly discuss the facts. On July 20, 1998, Mr. Bartsma pleaded guilty to one count of possession of a firearm by a convicted felon in violation of 18 U.S.C. § 922(g)(1).1 The Presentence Investigation Report listed Mr. Bartsma's base offense level at 20, as prescribed in U.S.S.G. § 2K2.1(a)(4)(A). A three-level downward adjustment was recommended for acceptance of responsibility under U.S.S.G. § 3E1.1(a) and (b) to reach a total offense level of 17. When the offense level was cross-referenced with the applicable criminal history category of IV,2 Mr. Bartsma's Guideline range stood at thirty-seven to forty-six months.

At the sentencing hearing the district court determined the criminal history category of IV did not adequately reflect either the seriousness of Mr. Bartsma's past criminal conduct, or the likelihood he would commit other crimes. Accordingly, the district court imposed an upward departure to category VI, and sentenced Mr. Bartsma to fifty-eight months imprisonment. The district court also sentenced Mr. Bartsma to three years of supervised release, and as a condition of the release required him to register as a sex offender in any state in which he resides. The district court justified the upward departure and the registration requirement by citing: (1) the nature of Mr. Bartsma's prior offenses, which include child molestation and rape; (2) Mr. Bartsma's history of prompt recidivism after being released for prior offenses; and (3) California's refusal to grant Mr. Bartsma parole on several occasions because he was viewed as a danger to the community.

Mr. Bartsma asserts several errors: (1) the district court abused its discretion by imposing the upward departure; (2) the district court failed to notify Mr. Bartsma it was considering imposing a sex offender registration requirement as a condition of supervised release; and (3) the district court abused its discretion by imposing the sex offender registration requirement as a condition of supervised release because the condition (sex offender registration) was not reasonably related to the nature or circumstances of the offense charged (possession of a firearm by a felon).

The analysis we use when reviewing Sentencing Guideline departures is well settled, and need not be spelled out exhaustively here. Following the Supreme Court's seminal case of Koon v. United States, 518 U.S. 81 (1996), we developed our general framework for reviewing Guideline departures in United States v. Collins, 122 F.3d 1297 (10th Cir. 1997). See United States v. Whiteskunk, 162 F.3d 1244, 1248-49 (10th Cir. 1998). The Guidelines specifically allow a sentencing court to depart from the otherwise applicable Guideline range "if the court finds 'that there exists an aggravating or mitigating circumstance of a kind, or to a degree, not adequately taken into consideration by the Sentencing Commission in formulating the guidelines.'" U.S.S.G. § 5K2.0 (quoting 18 U.S.C. § 3553(b)). The Guidelines make a distinction between a "heartland case," fully anticipated and covered by the applicable guideline, and an "atypical case," in which a departure may be warranted. See Koon, 518 U.S. at 93-94. "It is up to the district court to determine whether certain factors take the case out of the 'heartland,' and 'make a refined assessment of the many facts bearing on the outcome, informed by its vantage point and day-to-day experience in criminal sentencing.'" Whiteskunk, 162 F.3d at 1249 (quoting Koon, 518 U.S. at 98). This assessment "embodies the traditional exercise of discretion by a sentencing court," and in most cases is given "substantial deference." Koon, 518 U.S. at 98.

In reviewing a departure from the Guidelines, we must evaluate:

(1) whether the factual circumstances supporting a departure are permissible departure factors; (2) whether the departure factors relied upon by the district court remove the defendant from the applicable Guideline heartland thus warranting a departure; (3) whether the record sufficiently supports the factual basis underlying the departure; and (4) whether the degree of departure is reasonable.

Collins, 122 F.3d at 1303. We review all four steps of the departure analysis under a unitary abuse of discretion standard. Id. When the district court's decision to depart is based on factual findings, the decision is "entitled to substantial deference." Whiteskunk, 162 F.3d at 1249.

As we stated earlier, the district court departed upward from the applicable criminal history category of IV to a category of VI. The Sentencing Guidelines specifically encourage an upward departure when the district court concludes "the criminal history category does not adequately reflect the seriousness of the defendant's past criminal conduct or the likelihood that the defendant will commit other crimes." U.S.S.G. § 4A1.3. Because § 4A1.3 provides an encouraged basis for departure, we find the district court relied on permissible departure factors when imposing the upward departure. See Collins, 122 F.3d at 1304.

While conceding § 4A1.3 permits an upward departure for an under-represented criminal history category, Mr. Bartsma focuses on the last three steps of the Collins inquiry and contends the facts of this case are insufficient to remove him from the heartland of criminal history category IV, the record is insufficient to support the factual basis underlying the departure, and the departure was not reasonable. After reviewing the record before us, we conclude the district court did not abuse its discretion in deciding to depart upward. However, the district court failed to articulate sufficient findings to support the degree of the departure, and therefore we remand for resentencing.

The district court based its departure on Mr. Bartsma's "extensive criminal record involving repeated crimes of violence," and its determination he was "a repeat criminal who repeats ... quickly after his release into the community." The court also noted "the prison records received from California Department of Corrections reveal the defendant was not granted parole on several occasions because he was viewed as a danger to the community." The Presentence Investigation Report, which the district court adopted, supports these conclusions. Specifically, the report noted Mr. Bartsma had several juvenile adjudications, including a charge of child molestation and a charge of unlawful sexual intercourse with a minor, which went uncounted for the purposes of criminal history. In addition, Mr. Bartsma had shown an inability to stay out of trouble he was arrested on the sexual intercourse with a minor charge just two months after jurisdiction in the child molestation case terminated; he committed rape by force four months after being paroled from the confinement sentence he received for the sexual intercourse with a minor charge; he was arrested in the current case four months after serving his sentence on the rape charge.3 Finally, California Department of Corrections records indicated Mr. Bartsma had poor impulse control, sadistic impulses toward women, and had fantasies that included raping and torturing a woman. Given the record as a whole, and recognizing the district court's special competence in determining the unusualness of a case, see Collins, 122 F.3d at 1305, we are unable to say the district court abused its discretion in granting the upward departure. The district court provided a sufficient explanation, supported by specific facts in the record, for the departure.

Having upheld the district court's determination to depart upward, we now consider whether the extent of the departure from a category IV to a category VI was reasonable. Our review of the reasonableness of a district court's departure is deferential. See Whiteskunk, 162 F.3d at 1253; Collins, 122 F.3d at 1303. To adequately review a departure decision, we must examine the district court's stated reasons for the degree of departure, see United States v. Pool, 937 F.2d 1528, 1534 (10th Cir. 1991), "together with factors such as: 'the seriousness of the offense, the need for just punishment, deterrence, protection of the public, correctional treatment, the sentencing pattern of the Guidelines, the policy statements contained in the Guidelines, and the need to avoid unwarranted sentencing disparities.'" Collins, 122 F.3d at 1308-09 (quoting United States v. White, 893 F.2d 276, 278 (10th Cir. 1990) (citing 18 U.S.C. § 3742(e)(3) and 18 U.S.C. § 3553 (a))). In Collins, we clearly reaffirmed our existing case law requiring a district court to "specifically articulate reasons for the degree of departure" using any "reasonable methodology hitched to the Sentencing Guidelines," including "extrapolation from or analogy to the Guidelines." Id. at 1309 (quotation marks and citations omitted); see also Whiteskunk, 162 F.3d at 1253-54. This requirement of stating the reasons for the degree of departure is separate and distinct from the requirement that district courts explain why a departure is warranted. United States v. Flinn, 987 F.2d 1497, 1502 (10th Cir. 1993).

In the present case, the district court offered little more than conclusory statements in support of its degree of departure. In its Memorandum and Order ruling on Mr. Bartsma's objections to the Presentence Report, the district court stated:

Based on the materials in the Presentence Report, the court concludes that the defendant's criminal history category of IV significantly under represents the seriousness of his prior criminal conduct and the likelihood that he will commit other crimes. [The court then lists the aforementioned factors used to justify the upward departure.] Under the circumstances, the court concludes that a criminal history category of VI more accurately reflects the seriousness of the defendant's criminal history and the likelihood of future crimes.

The district court made a similar oral ruling during the sentencing hearing. The district court's statements mirror similar justifications we have held in the past to be insufficiently particular to support a degree of departure. See Whiteskunk, 162 F.3d at 1254; United States v. Okane, 52 F.3d 828, 837 (10th Cir. 1995); United States v. Yates, 22 F.3d 981, 987-88, 991 (10th Cir. 1994); Flinn, 987 F.2d at 1503-04; United States v. Kalady, 941 F.2d 1090, 1100 (10th Cir. 1991); Pool, 937 F.2d at 1533-34. The factors listed by the district court the nature of past offenses, the history of recidivism, and the likelihood Mr. Bartsma would commit future crimes were sufficient to support a departure from the Guideline range, but "this does not automatically suffice to explain the degree of departure." Whiteskunk, 162 F.3d at 1253.

As was the case in Whiteskunk, we find nothing in the record, the presentence report, or the sentencing transcript which provides any explanation or methodological basis for how the district court arrived at an upward departure of two criminal history categories. Id. We often have stated the district court is not required to justify the degree of departure with mathematical precision, but the court is required to include in its justification "some method of analogy, extrapolation or reference to the sentencing guidelines." United States v. O'Dell, 965 F.2d 937, 939 (10th Cir. 1992). To employ our degree of departure reasonableness analysis when the district court has failed to so reference the Guidelines would render our review difficult, if not impossible, and we would be left to speculate as to why the sentencing court imposed a particular sentence. See Whiteskunk, 162 F.3d at 1253; United States v. Gardner, 905 F.2d 1432, 1436 (10th Cir.), cert. denied, 498 U.S. 875 (1990).

Given our inability to determine whether the degree of departure was reasonable, we must remand for resentencing. Mindful of the multitude of tasks required of our district courts at sentencing, we nevertheless again implore them to precisely lay out their reasoning and analysis as to why they selected a particular degree of departure.

II. The Special Condition of Supervised Release Sex-Offender Registration

Mr. Bartsma's final two arguments center around the district court's imposition of the special condition of supervised release requiring him to register as a sex offender. First, Mr. Bartsma contends he was entitled, as a matter of law, to presentence notice the condition was under consideration. Second, Mr. Bartsma argues the district court erred by imposing the condition because there was no reasonable relationship between the condition and the crime of possession of a firearm by a felon. We review conditions of supervised release for abuse of discretion. United States v. Edgin, 92 F.3d 1044, 1047 (10th Cir. 1996), cert. denied, 519 U.S. 1069 (1997).

Before deciding whether presentence notice was required, we first must determine whether Mr. Bartsma preserved the issue for appeal. The Government argues defense counsel failed to object to the condition, or the lack of notice, and therefore our review should be for plain error. See United States v. Fabiano, 169 F.3d 1299, 1307 (10th Cir. 1999), cert. denied, ___ U.S. ___, 120. Defense counsel admittedly did not lodge a formal objection.4 However, we conclude Mr. Bartsma did not waive his objections to the special condition even if he did not assert them at the district court. We decided a similar issue in Edgin, 92 F.3d at 1044, and find that case instructive.

In Edgin, the district court imposed a special condition of release that prevented Mr. Edgin from contacting his son. Edgin, 92 F.3d at 1047. The court imposed the condition near the end of the hearing, after Mr. Edgin had made his final statement and the court had resolved the objections to the presentence report. Id. at 1049. Mr. Edgin did not object to the special condition at the sentencing hearing, arguing for the first time on appeal the district court acted outside its statutory authority in imposing the condition. Id. at 1048. Citing the requirements of Rule 32(c)(1) of the Federal Rules of Criminal Procedure,5 and noting Mr. Edgin was given no opportunity to comment on or notice of the special condition, we held Mr. Edgin did not waive his attack by failing to assert it at the trial court. Id. at 1048-49. The same reasoning is applicable to the specific facts of the case before us. Mr. Bartsma had no notice the district court was considering the special condition until the court stated its tentative sentence near the beginning of the sentencing hearing. Mr. Bartsma was afforded an opportunity to comment on the condition as evidenced by his attorney's questions to the court. However, as in Edgin, the complete lack of notice made it impossible for the parties to anticipate the nature of the special condition and short-circuited the significance of any opportunity to comment. See generally Burns v. United States, 501 U.S. 129, 134 (1991) (describing the function of Rule 32 as providing for "focused, adversarial development of the factual and legal issues relevant to determining the appropriate Guidelines sentence."). Moreover, this case is distinguishable from Fabiano, where we reviewed the imposition of a similar condition of release for plain error when Mr. Fabiano did not object to the condition at the sentencing hearing. Fabiano, 169 F.3d at 1307. In Fabiano, the Presentence Report specifically listed compliance with a sex offender registration law as a possible special condition for the district court to consider. Id. at 1308. Mr. Bartsma was afforded no such notice in this case. Given these circumstances, Mr. Bartsma did not waive his challenges to the special condition by failing to raise them at the sentencing hearing.

We now turn to the question of whether Mr. Bartsma was entitled to notice before the district court imposed the special condition ordering him to register as a sex offender. Having found no controlling authority directly on point, we analyze this issue as one of first impression. The only other Circuit to decide the issue applied Rule 32 and the Supreme Court's decision in Burns to hold reasonable presentence notice was required. See Coenen, 135 F.3d at 943. We reach the same conclusion here.

In Burns, the Supreme Court held Rule 32 required reasonable notice to the parties when a district court is contemplating an upward departure based on a ground not listed in either the presentence report or a prehearing submission by the Government. Burns, 501 U.S. at 138-39. As mentioned previously, Rule 32(c)(1) states, in part: "At the sentencing hearing, the court must afford counsel for the defendant and for the Government an opportunity to comment on the probation officer's determinations and on other matters relating to the appropriate sentence." Fed. R. Crim. P. 32(c)(1). The Court in Burns reasoned that allowing district courts to depart from the Guidelines sua sponte without first affording notice to the parties would render "meaningless the parties' express right [under Rule 32] to comment upon ... matters relating to the appropriate sentence." Burns, 501 U.S. at 136 (quotation marks and citation omitted.). The Court went on to say: "'Th[e] right to be heard has little reality or worth unless one is informed' that a decision is contemplated." Id. (quoting Mullane v. Central Hanover Bank & Trust Co., 339 U.S. 306, 314 (1950)).6 Not requiring notice would be "inconsistent with Rule 32's purpose of promoting focused, adversarial resolution of the legal and factual issues relevant to fixing Guidelines sentences." Id. at 137. In Edgin, we implied this same rationale was applicable to special conditions of supervised release when we held Mr. Edgin had not waived his right to appeal, in part because he was "afforded no notice of ... the special condition." Edgin, 92 F.3d at 1049 (citing Rule 32 and Burns). Today we expressly conclude the Burns rationale applies when a district court is considering imposing a sex offender registration requirement as a special condition of supervised release, and the condition is not on its face related to the offense charged.

We find further support for our position in the statutes. 18 U.S.C. § 3555 allows a district court to order defendants convicted of offenses involving fraud or other intentionally deceptive practices to notify their victims of the existence and nature of their conviction. When a district court plans to order notice pursuant to § 3555, presentence notice to the parties is required: "Prior to imposing an order of notice pursuant to section 3555, the court shall give notice to the defendant and the Government that it is considering imposing such an order." 18 U.S.C. § 3553(d); see also Coenen, 135 F.3d at 941-42. This requirement not only allows the parties to properly develop relevant issues related to the notice requirement, but it also affords the court an opportunity to specify its reasons for imposing such a requirement. See 18 U.S.C. § 3553(d)(1) - (3). All parties involved, including this court, would benefit from such a procedure when a district court is considering imposing a special condition of supervised release which includes a sex offender registration requirement.

We conclude Mr. Bartsma was entitled to receive reasonable presentence notice, either from the Presentence Report, a prehearing submission from the Government, or the district court itself, that a special condition of supervised release requiring him to register as a sex offender was a possibility.7 Mr. Bartsma is obviously on notice now, and all parties should be prepared to address this issue on remand.

Having determined Mr. Bartsma was entitled to notice, we do not reach the issue of whether the district court abused its discretion by imposing the sex offender registration requirement in this case. We do note the record before us is void of any findings or a determination by the district court that the special condition was reasonably related to the current offense. District courts enjoy broad discretion in fashioning conditions of supervised release. Edgin, 92 F.3d at 1048. However, the conditions must

"involve no greater deprivation of liberty than is reasonably necessary' to deter criminal conduct, protect the public, and provide the defendant with needed educational or vocational training, medical care, or other correctional treatment.... [T]he conditions must [also] be 'reasonably related' to 'the nature and circumstances of the offense and the history and characteristics of the defendant."

Fabiano, 169 F.3d at 1307 (quoting 18 U.S.C. §§ 3583(d), 3583(d)(1), 3553(a)(1) - (2)). An appellate court should not be left to speculate about the nexus between the condition and the nature and circumstances of the offense. See Edgin, 92 F.3d at 1049. We trust the parties will argue this point on remand in order to allow the district court to make sufficient findings in support of any condition of supervised release the court may impose.

In conclusion, we hold the district court did not abuse its discretion by imposing an upward departure from the Sentencing Guidelines. The record is clearly sufficient to support such a decision. However, the district court failed to adequately justify the degree of departure. In addition, Mr. Bartsma was entitled to presentence notice the district court was considering imposing a sex offender registration requirement as a special condition of supervised release. Therefore, we remand for resentencing with instructions to the district court to provide sufficient findings in support of the methodology used to determine the degree of departure. Remand is necessary also to afford Mr. Bartsma the presentence notice he is entitled to, and will allow both parties the opportunity to argue the propriety and the practicalities of sex offender registration in this case.

Accordingly, we AFFIRM the district court's upward departure, VACATE the sentence, and REMAND to the district court for resentencing in a manner consistent with this opinion.